# Optimal choice P65534

Statement

thehtml

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 wi and value vi. 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 wi, vi. Assume 1 ≤ W ≤ 1012, 1 ≤ n ≤ 100, 1 ≤ wiW, and 1 ≤ vi ≤ 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