Baraj II
Problema 3

La cules de mere

Pe o creanga a unui mar se afla n mere. Fiecare al i-lea mar este caracterizat prin greutate si distanta de la sol la care se afla. Un culegator doreste sa adune o cantitate cat mai mare de mere.
El stie ca atunci cand rupe un mar de pe creanga, aceasta se va ridica cu x cm (deci fiecare mar din cele ramase, se va ridica, impreuna cu creanga, cu x cm). Culegatorul neavand scara, nu poate culege mere care se afla la o inaltime mai mare decat o inaltime maxima data.
Determinati ordinea in care vor fi culese merele, astfel incat la sfarsit (adica in momentul in care nu mai exista mere accesibile) greutatea totala a merelor culese sa fie maxima.

Date de intrare:
Pe prima linie a fisierului MERE.IN este scris un triplet:
n x hmax
unde:
n - reprezinta numarul de mere de pe creanga (1<=n<=8000);
x - reprezinta distanta cu care se ridica creanga dupa ce se culege oricare mar (1<=x<=10000);
hmax - reprezinta inaltimea maxima la care poate ajunge culegatorul (1<=hmax<=10000).
Pe urmatoarele n linii sunt scrise perechi de numere naturale:
g_i h_i
unde:
g_i - reprezinta greutatea celui de al i-lea mar (1<=g_i<=60000);
h_i - reprezinta distanta de la sol a celui de al i-lea mar (1<=h_i<=10000).

Date de iesire:
Pe prima linie a fisierului MERE.OUT se scrie o pereche de numere naturale:
gmax nr
unde:
gmax - reprezinta greutatea maxima, posibila de cules;
nr - reprezinta numarul de mere (ale caror greutati totalizeaza gmax);
Pe urmatoarele nr linii se scriu perechi de numere naturale:
g h
unde:
gk - reprezinta greutatea celui de al k-lea mar cules;
hk - reprezinta inaltimea initiala al celui de al k-lea mar cules.
Ordinea scrierii in fisier trebuie sa corespunda cu ordinea in care au fost culese merele.

Exemplu:

MERE.IN
4 10 100
10 95
12 93
10 84
5 80
MERE.OUT
27 3
12 93
10 84
5 80

Timp maxim de executare/test: 2 secunde.
Punctaj maxim: 50 puncte.