== include(page="template/taskheader" task_id="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.
Poveste şi cerinţă...
h2. 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: $S{~i~}$ şi $N{~i~}$, reprezentând satisfacţia respectiv neplăcerea produse de cel de-al $i$-lea cd.
Fişierul de intrare $ephie.in$ ...
h2. 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.
În fişierul de ieşire $ephie.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 1 000 000$
* $K ≤ N$
* $0 ≤ S{~i~}$
* $0 ≤ N{~i~}$
* 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.
* Satisfacţia netă reprezintă suma satisfacţiilor corespunzătoare cdurilor care sunt ascultate din care se scade suma neplăcerilor corespunzătoare cdurilor scoase din teanc şi neascultate.
* Satisfacţia netă se încadrează pe 32 de biţi cu semn.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. ephie.in |_. ephie.out |
| 4 2
1 1
3 2
3 1
1 1
| 5
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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 $N{~1~} + S{~2~} + S{~3~} = (-1) + 3 + 3 = 5$.
...
== include(page="template/taskfooter" task_id="ephie") ==
