FC Campion Romania se pregateste
pentru finala Ligii Campionilor Europeni. Pentru aceasta, cei N
jucatori ai sai se antreneaza zilnic. Pentru fiecare dintre ei se cunoaste intervalul
[T1,T2)
când este prezent la antrenament. Pentru ca antrenamentul sa fie mai eficient,
jucatorii nu se antreneaza toti la un loc, ci sunt împartiti în
K echipe. Fiecare jucator face
parte din exact o echipa, dar este posibil ca din unele echipe sa nu faca parte
nici un jucator. Deoarece munca în echipa este foarte importanta, antrenamentul
fiecareia dintre cele K echipe
se poate desfasura numai daca sunt prezenti toti jucatorii care fac parte din
acea echipa. În aceste conditii, durata de antrenament a fiecarei echipe
este egala cu lungimea intervalului de timp în care sunt prezenti la antrenament
toti jucatorii din echipa respectiva. Întrucât finala se apropie,
conducerea clubului doreste ca suma duratelor de antrenament ale fiecarei echipe
sa fie maxima.
Cerinta
Determinati o împartire
în K echipe a celor N
jucatori, astfel încât suma duratelor de antrenament sa fie maxima.
Date de intrare
Pe prima linie a fisierului
echipe.in se afla doua numere
întregi, separate prin spatii: N
si K. Pe urmatoarele N
linii se afla câte doua numere întregi separate prin spatii, A
si B, reprezentând intervalele
de timp în care sunt prezenti jucatorii la antrenament.
Date de iesire
În fisierul echipe.out
veti afisa suma maxima a duratelor de antrenament corespunzatoare unei împartiri
pe echipe optime.
Restrictii si precizari
· 1
<= K <= N <= 250
· 0 <= A < B <= 1 000
000
· Daca o echipa contine 0 jucatori, durata ei de antrenament este 0.
· Daca nu exista nici un moment în care toti jucatorii unei echipe
sa fie prezenti simultan la antrenament, atunci durata de pregatire a echipei
respective este 0.
Exemplu
echipe.in
echipe.out
Explicatie
8 4
0 11
0 10
1 11
2 12
3 13
4 14
5 15
19 28
36
Din prima echipa fac
parte jucatorii 1, 2 si 3. Din a doua echipa vor face parte jucatorii
4 si 5. Din a treia echipa fac parte jucatorii 6 si 7, iar a patra echipa
îl va contine doar pe jucatorul 8. Intervalele de antrenament pentru
fiecare din cele 4 echipe sunt: [1,10) , [3,12) , [5,14) , [19,28).