Knapsack

The input consists of several test cases. Each test case begins with a real number $C \le 2\, 000$ giving the capacity of the knapsack, and an integer $n \le 2\, 000$, giving the number of objects. Then follow $n$ lines, each giving the value and weight of the $n$ objects. Both values and weights will be integers between $1$ and $10\, 000$.

For each test case, output a line containing the number of items chosen, followed by a line containing the indices of the chosen items (the first item has index $0$, the second index $1$, and so on). The indices can be given in any order.

Sample Input 1 | Sample Output 1 |
---|---|

5.3 3 1 5 10 5 100 5 6.1 4 5 4 4 3 3 2 2 1 |
1 2 3 1 2 3 |