Train
Национална Олимпиада по Информатика 2014, Контрола 2
Time Limit: 0.2s, Memory Limit: 64MiB
Ели експериментира с различни професии, с които не бихте очаквали тя да се занимава. Например, в момента тя е машинист на влак.

За да пътуват с нейния влак, N потенциални пътници предварително са направили заявка за билет, указвайки къде биха се качили и къде биха слязли, ако получат билет. Тъй като маршрутът на влака е предварително фиксиран, можем да номерираме неговите L спирки с числата от 1 до L, включително. Така всеки потенциален пътник i задава две числа Bi и Ei - спирката, на която би се качил, и спирката, на която би слязъл.

Транспортната фирма, за която работи Ели, БДЖ (Баварски Държавни Железници) има фиксирана цена на билетите, без значение къде се качват и за колко спирки пътуват пътниците. Също така, влакът има определен капацитет - по всяко време той може да вози най-много M човека (като Ели не влиза в тази бройка).

Ели работи на процент от спечелените пари, в следствие на което е на изгода да удовлетвори заявките на възможно най-голям брой пътници (колкото повече продадени билети – толкова повече приходи). Помогнете й, като намерите колко е този брой. Не забравяйте, че пътниците, получили билет, трябва да са така подбрани, че в никой момент да не се надхвърли капацитета на влака M. Считаме, че на всяка спирка първо слизат хората, чието пътуване завършва там, а после се качват тези, чието пътуване започва там.
Вход
На първия ред на стандартния вход ще бъдат зададени три цели числа N, M, и L – съответно броя хора, задали заявка за билет, максималния капацитет на влака, и броя спирки. Следват N на брой реда, всеки съдържащ по две цели числа Bi и Ei, указващи, съответно, спирката на която би се качил и спирката на която би слязъл i-тият пътник.
Изход
На единствен ред на стандартния изход изведете едно цяло число – максималния брой билети, които момичето може да продаде.
Ограничения
  • 1 ≤ N, M ≤ 100,000
  • 1 ≤ Bi < EiL ≤ 1,000,000,000
Примерен Вход Примерен Изход
5 2 10 2 4 3 7 1 2 1 8 5 9 4
Има 5 човека, които искат да закупят билет. Влакът побира максимум двама допълнителни пътника освен Ели (явно е спортен модел). Едно възможно решение е Ели да вземе пътниците (1, 2), (1, 8), (2, 4), и (5, 9). Така от спирка 1 се качват (1, 2) и (1, 8). На спирка 2 слиза (1, 2) и се качва (2, 4). На спирка 4 слиза (2, 4). На спирка 5 се качва (5, 9). На спирка 8 слиза (1, 8). На спирка 9 слиза (5, 9).
Мрън!