gutui

Gutui

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

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.

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

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.

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

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

* H, U, greutatea maxima culeasa de Gigel, greutatile si inaltimile gutuilor < 2^31
* O solutie O(N*N) obtine ~80% din teste.

* $H$, $U$, greutatea maxima culeasa de Gigel, greutatile si inaltimile gutuilor sunt $< 2^31^$
* O solutie $O(N^2^)$ obtine $~80%$ din teste.

h2. Exemplu

h2. Exemple

table(example). |_. gutui.in |_. gutui.out |

table(example). |_. gutui.in |_. gutui.out |_. gutui.in |_. gutui.out |

| 4 100 10
  91 10
  82 30
  93 5
  94 15
| 45

|
 
table(example). |_. gutui.in |_. gutui.out |
| 9 100 10

|9 100 10

  40 2
  20 1
  70 1

  60 3
  30 2
  50 2

| 17
|

|17|

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.

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