Fişierul intrare/ieşire:gutui.in, gutui.outSursăad-hoc
AutorAdăugată desvalentinValentin Stanciu svalentin
Timp execuţie pe test0.4 secLimită de memorie12120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gutui

Gigel are in curte un gutui. El se hotaraste sa culeaga cat mai multe gutui, dar are o problema: copacul este atat de incarcat cu fructe incat la fiecare gutuie culeasa, toate crengile acestuia se ridica in inaltime cu fix U centimetrii. Din pacate Gigel nu are scara la el si nu poate sa culeaga gutui la o inaltime mai mare de H centimetrii.

Nici de aceasta data Gigel nu se descurca singur. Ajutati-l sa culeaga cat mai multe gutui.

Stiind greutatea si inaltimea initiala a fiecarui fruct, se cere cea mai mare recolta de gutui pe care o poate aduce Gigel acasa. Cum se gandeste sa le vanda in piata, il intereseaza o greutate cat mai mare, nu un numar cat mai mare.

Date de intrare

Pe prima linie a fisierului de intrare gutui.in se afla 3 numere intregi: N (numarul de gutui din copac), H (inaltimea maxima la care ajunge Gigel) si U (cu cat se ridica crengile copacului dupa culegerea unei gutui).
Pe urmatoarele N linii se afla cate 2 numere intregi reprezentand inaltimiile si greutatile gutuilor din copac.

Date de ieşire

In fisierul de iesire gutui.out trebuie scrisa greutatea maxima a gutuilor pe care le poate culege Gigel.

Restricţii

  • 1 ≤ N ≤ 100000
  • H, U, greutatea maxima culeasa de Gigel, greutatile si inaltimile gutuilor sunt < 231
  • O solutie O(N2) obtine ~80% din teste.

Exemple

gutui.ingutui.outgutui.ingutui.out
4 100 10
91 10
82 30
93 5
94 15
45
9 100 10
40 2
20 1
70 1
80 3
50 1
30 2
60 3
30 2
50 2
17

Explicatie

In primul exemplu se culege intai gutuia de greutate 15 si apoi gutuia de greutate 30. In al doilea exemplu se culeg toate gutuile.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?