echipe

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).

Timp maxim de executie/test: 0.1 secunde

Andreica Mugurel Ionut
Universitatea Politehnica Bucuresti
Contact: mugurel_ionut at yahoo dot com