Motxilla amb pesos i valors P27895

Teniu una motxilla que aguanta fins a $p$ unitats de pes. Donats $n$ objectes, cadascun amb un pes $p_i$ i un valor $v_i$, 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 $p_i$ $v_i$. Suposeu $1 \le p \le 1000$, $1 \le n \le 1000$, $1 \le p_i \le p$, i $1 \le v_i \le 10^6$.

Sortida

Per a cada cas, escriviu el màxim valor dels objectes que es poden guardar a la motxilla.