Optimal choice P65534


Statement
 

pdf   zip

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 ≤ wi ≤ W, 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
    Salvador Roura
    Language
    English
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++