Într-o tabără de vară se programează susținerea unor cursuri în K săli de clasă. Sunt N profesori care și-au exprimat dorința de a participa, fiecare dintre ei specificând intervalul de timp [ai, bi] în care își poate susține cursul. Programarea pe săli a profesorilor trebuie să țină cont de faptul că într-o clasă, la un moment dat, nu poate preda decât un singur profesor.

Cerința

Cunoscându-se faptul că organizatorii doresc susținerea a cât mai multor cursuri, să se determine:

1) Numărul maxim de cursuri care pot fi programate în cele K săli de clasă, ținând cont de restricția indicată.
2) În dorința de a programa toate cursurile, în cele K săli, organizatorii decid să modifice durata cursurilor, păstrând însă neschimbată ora de început a lor. Astfel, ei hotărăsc ca toate cursurile să dureze un interval egal de timp, care însă nu va depăși durata celui mai lung curs propus inițial de unul dintre cei N profesori. Determinați care poate fi durata maximă pe care o pot avea cursurile în aceste condiții.

Date de intrare

Fișierul de intrare cursuri.in conține pe prima linie un număr natural C. Pentru toate testele, C poate lua numai valorile 1 sau 2. Pe linia a doua se găsește o pereche de numere naturale N K, separate printr-un spațiu, reprezentând numărul profesorilor și numărul de săli de clasă. Pe următoarele N linii se găsesc perechi de numere naturale ai, bi, care reprezintă intervalele de timp în care cei N profesori își susțin cursurile. Numerele în cadrul unei linii sunt separate printr-un spațiu.

Date de ieșire

Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire cursuri.out va conține pe prima linie un număr natural reprezentând numărul maxim de cursuri care pot fi programate în cele K săli de clasă, ținând cont de restricția indicată.

Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire cursuri.out va conține pe prima linie un număr natural reprezentând durata maximă pe care o pot avea cele N cursuri, astfel încât toate să poată fi susținute în cele K săli disponibile.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ K ≤ 1 000
• 1 ≤ ai < bi ≤ 100 000, unde 1 ≤ i ≤ N
• În cazul cerinței 2) se garantează că pentru toate testele există soluție
• Pentru rezolvarea corectă a primei cerinţe se acordă 45 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 45 de puncte. Se acordă 10 puncte pentru exemple.

Exemplul 1

cursuri.in

1
4 2
2 16
1 3
3 18
1 20

cursuri.out

3

Explicație

O variantă de programare optimă este următoarea:

• în prima sală se vor susține cursurile programate între [1,3] şi [3,18]
• în a doua clasă se susține cursul programat între [1,20]

Exemplul 2

cursuri.in

2
4 2
5 12
9 18
1 3
1 7

cursuri.out

4

Explicație

Durata maximă pe care o pot avea toate cursurile este 4.

Cursul al treilea se va mări și se va desfășura între [1,5], celelalte se vor micșora. Cursurile vor fi distribuite în cele două săli astfel:

• Sala 1: al treilea și primul profesor programați între [1,5] respectiv [5,9];
  Sala 2: al patrulea și al doilea profesor programați între [1,5] respectiv [9,13];