Fişierul intrare/ieşire:ephie.in, ephie.outSursăTabăra ICHB 2012, Ziua 1, Grupa 1
AutorPetru TrimbitasAdăugată despatarelDan-Constantin Spatarel spatarel
Timp execuţie pe test0.7 secLimită de memorie36480 kbytes
Scorul tăuN/ADificultateN/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
  • 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.
  • 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.

Exemplu

ephie.inephie.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?