| Fişierul intrare/ieşire: | gutui.in, gutui.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Valentin Stanciu •svalentin | |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 12120 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | gutui.out | gutui.in | gutui.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.
