McDonald’s

Cerință

Munca la McDonald's a devenit puțin mai dificilă în ultimul timp. Donald Pump, faimosul american, s-a angajat recent la un Mc din Texas. Lui i se dă o grămadă formată din $N$ cartofi prăjiți, pe care îi înșiră cu tandrețe unul lângă altul. Fiecare cartof este caracterizat de o greutate $G$, și o frumusețe $F$, ambele exprimate prin două numere naturale. Cetățenii americani, ca de obicei, cer mâncare și sunt foarte fițoși. D. Pump vă cere să găsiți cât de rapid posibil o submulțime de cartofi astfel încât suma frumuseților acestora să fie maximă, iar suma greutăților să nu depășească o valoare $G$ dată. (fiindcă Pump este un om serios și nu vrea să fie prea generos cu cetățenii).

Date de intrare

Pe prima linie a fişierului mcdonalds.in se vor găsi valorile $N$ si $G$, cu semnificația din enunț. Pe următoarele $N$ linii se vor găsi perechile de valori $G_i$ și $F_i$, reprezentând greutatea, respectiv frumusețea cartofului prăjit cu indicele $i$.

Date de ieșire

Pe prima linie a fişierului mcdonalds.out se va afișa o singură valoare $Fmax$, frumusețea maximă care poate fi obținută respectând cerința problemei.

Restricții și precizări

• $2 \leq N \leq 5 \ 000$
• $1 \leq G \leq 10 \ 000$
• $1 \leq G_i, F_i \leq 10 \ 000$
• $Fmax \leq G$

Exemplul 1

mcdonalds.in

5 8
2 6
3 5
4 7
1 3
5 9

mcdonalds.out

18

Explicație

D. Pump ia cartofii cu indicii $1$, $4$ și $5$, a căror greutate este $8$. Aceștia au suma frumuseților $6 + 3 + 9 = 18$.

Exemplul 2

mcdonalds.in

3 7
4 1
2 2
1 6

mcdonalds.out

9

Explicație

În acest caz, D. Pump ia toți cartofii, deoarece suma greutăților este exact $7$. Aceștia au suma frumuseților $1 + 2 + 6 = 9$.