== 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ă 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.

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.

h2. 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]$.

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.

h2. Date de ieşire

În fişierul de ieşire $ephie.out$ se află profitul maxim care se poate obţine

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

h2. Restricţii
* $1 ≤ N ≤ 1 000 000$

* $1 ≤ K ≤ 1 000$
* Răspunsul se încadrează pe 32 biţi

* $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

h3. Explicaţie

Ea scoate primul cd din teanc si le ascultă pe următoarele 2, profitul fiind 3+3-1.

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") ==