Cerința

Într-un magazin intergalactic sunt n tipuri de obiecte, o infinitate din fiecare; pentru fiecare se cunoaște greutatea G și valoarea V. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax. El va fura anumite obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

Să se stabilească câștigul maxim pe care îl poate obține hoțul. Câștigul este egal cu suma valorilor obiectelor furate.

Date de intrare

Programul citește de la tastatură numerele naturale n și GMax, iar apoi n perechi de valori G V, reprezentând greutatea, respectiv valoarea fiecărui tip de obiect.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.

Restricții și precizări

• 1 ≤ n ≤ 1 000;
• 1 ≤ G, V, GMax ≤ 10 000.

Exemplu:

Intrare

4 10
6 30
3 14
4 16
2 9

Ieșire

48

Explicație

Hoțul poate lua un obiect de tipul 1 și două obiecte de tipul 4 ($30+2*9 = 48$)