Backpack with weights and values P27895

You have a backpack that can bear up to $w$ units of weight. Given $n$ objects, each with a weight $w_i$ and a value $v_i$, compute the maximum sum of values achievable, in such a way that the sum of weights does not exceed $w$. Take into account that objects cannot be cut: either you pick them, or you discard them.

Input

Input consists of several cases. Every case begins with $w$ and $n$, followed by $n$ pairs of integer numbers $w_i$ $v_i$. Assume $1 \le w \le 1000$, $1 \le n \le 1000$, $1 \le w_i \le p$, and $1 \le v_i \le 10^6$.

Output

For every case, print the maximum value of the objects that can be stored in the backpack.