Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ephie.in, ephie.out | Sursă | Tabăra ICHB 2012, Ziua 1, Grupa 1 |
| Autor | Petru Trimbitas | Adăugată de |  Dan-Constantin Spatarel •spatarel |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 36480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ephie
Ephie are acasă o colecţie de N cduri cu muzică bună. Deoarece ea nu e foarte ordonată le păstrează aşezate unele peste altele. Fiecare cd are un profit(satisfacţia pe care o produce dacă este ascultat) şi un cost(cât se deteriorează dacă este scos din teanc şi nu este ascultat).
Deoarece ea ţine foarte mult la cdurile sale, dar vrea să şi asculte muzică bună, ea vă roagă să calculaţi profitul maxim de a asculta K cduri din colecţie.
Date de intrare
Fişierul de intrare ephie.in conţine N numărul de cduri si K, câte cduri trebuie alese. Pe următoarele N linii se află câte 2 numere, p[i] şi c[i].
Date de ieşire
În fişierul de ieşire ephie.out se află profitul maxim care se poate obţine
Restricţii
- 1 ≤ N ≤ 1 000 000
- 1 ≤ K ≤ 1 000
- 1 ≤ p i, c i ≤ 2 000
Exemplu
| ephie.in | ephie.out |
|---|---|
| 4 2 1 1 3 2 3 1 1 1 | 5 |
Explicaţie
Ea scoate primul cd din teanc si le ascultă pe următoarele 2, profitul fiind 3+3-1.
