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^{6}.

Output

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

Public test cases

**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

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python Python
- User solutions
- C++