cursuri

Î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 [$a_i, b_i$] î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ță

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

În fișierul de intrare cursuri.in se găsește 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 $a_i \ b_i$, 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 \leq N \leq 1 \ 000$;
• $1 \leq K \leq 1 \ 000$;
• $1 \leq a_i < b_i \leq 100 \ 000$;
• Î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 din oficiu.

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]$;