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 ≤ w ≤ 1000, 1 ≤ n ≤ 1000, 1 ≤ w_i ≤ p, and 1 ≤ v_i ≤ 10⁶.

Output

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