== include(page="template/taskheader" task_id="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 manance 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.
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.
h2. Date de intrare
Fişierul de intrare $gutui.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $gutui.out$ ...
In fisierul de iesire $gutui.out$ trebuie scrisa greutatea maxima a gutuilor pe care le poate culege Gigel.
h2. Restricţii
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. gutui.in |_. gutui.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* $1 ≤ N ≤ 100000$
* $H$, $U$, greutatea maxima culeasa de Gigel, greutatile si inaltimile gutuilor sunt $< 2^31^$
* O solutie $O(N^2^)$ obtine $~80%$ din teste.
h2. Exemple
table(example). |_. 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|
h3. Explicaţie
h3. 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.
== include(page="template/taskfooter" task_id="gutui") ==
