Teniu una motxilla que aguanta fins a p unitats de pes. Donats n objectes, cadascun amb un pes pi i un valor vi, calculeu la suma màxima de valors que es pot aconseguir, de manera que la suma de pesos no passi de p. Tingueu en compte que els objectes no es poden partir en trossos: o s’agafen, o es descarten.
Entrada
L’entrada consisteix en diversos casos. Cada cas comença amb p i n, seguits de n parells d’enters pi vi. Suposeu 1 ≤ p ≤ 1000, 1 ≤ n ≤ 1000, 1 ≤ pi ≤ p, i 1 ≤ vi ≤ 106.
Sortida
Per a cada cas, escriviu el màxim valor dels objectes que es poden guardar a la motxilla.
Pista
Inspireu-vos en el problema d’aconseguir un cert canvi amb un conjunt de monedes donat. Fixeu-vos que els pesos són enters, i relativament petits.
Input
10 3 7 3000 8 4000 3 2000 10 3 7 3000 8 6000 3 2000 2 4 1 3 1 5 1 7 1 7
Output
5000 6000 14