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ă pe toate aşezate unele peste altele. Fiecare cd poate aduce o satisfacţie (dacă este ascultat) sau o neplăcere (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ă, vă roagă să calculaţi satisfacţia netă maximă pe care o poate avea, ascultând K cduri din colecţie.
Date de intrare
Fişierul de intrare ephie.in conţine pe prima linie N - numărul de cduri din colecţie si K - câte cduri vor fi ascultate. Pe fiecare din următoarele N linii se află câte 2 numere: Si şi Ni, reprezentând satisfacţia respectiv neplăcerea produse de cel de-al i-lea cd.
Date de ieşire
În fişierul de ieşire ephie.out se va găsi un singur număr întreg, reprezentând satisfacţia netă maxim care se poate obţine.
Restricţii
- 1 ≤ N ≤ 1 000 000
- 1 ≤ K ≤ 1 000
- K ≤ N
- 0 ≤ Si
- 0 ≤ Ni
- Pentru a putea asculta cel de-al i-lea cd, Ephie trebuie să scoată din teanc cdurile 1, 2, ..., i.
- Suma tuturor satisfacţiilor şi suma tuturor neplăcerilor se încadrează pe 32 de biţi cu semn.
- Răspunsul se încadrează pe 32 de biţi cu semn.
Exemplu
| ephie.in | ephie.out |
|---|---|
| 4 2 1 1 3 2 3 1 1 1 | 5 |
Explicaţie
Ea scoate primele 3 cduri din teanc, îl dă deoparte pe primul si le ascultă pe următoarele două, satisfacţia netă fiind N1 + S2 + S3 = (-1) + 3 + 3 = 5.
