Angel, a good friend of yours, has a truck that can transport a maximum weight *W*.
He has *n* objects at home, each with weight *w*_{i} and value *v*_{i}.
He will depart, so he wants to pick the most valuable subset of objects
with total weight no larger than *W*.
However, Angel does not like to compute optimal solutions.
Can you help him?

**Input**

Input consists of several cases with only integer numbers.
Every case begins with *W* and *n*,
followed by *n* pairs *w*_{i}, *v*_{i}.
Assume 1 ≤ *W* ≤ 10^{12},
1 ≤ *n* ≤ 100,
1 ≤ *w*_{i} ≤ *W*,
and 1 ≤ *v*_{i} ≤ 100.

**Output**

For every case, print three lines. On the first, print the largest possible total value. On the second, print the number of objects of the optimal subset. On the third, print in increasing order and separated by spaces the indices (starting at one) of the chosen objects. If there is more than one optimal solution, you can choose any one.

Public test cases

**Input**

10000 3 5000 20 8000 27 4000 10 10000 3 5000 20 8000 100 4000 10 1000000 2 900000 10 100000 20 1000000000000 10 100000000000 1 200000000007 2 300000000000 3 400000000001 4 500000000003 5 100000000000 1 200000000000 2 300000000000 3 400000000005 4 500000000000 5

**Output**

30 2 1 3 100 1 2 30 2 1 2 10 3 7 8 10

Information

- Author
- Salvador Roura
- Language
- English
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++
- Event
- Tretzè Concurs de Programació de la UPC - Final
- Date
- 2015-09-16