Start

2018-05-07 00:00 UTC

CFT3

End

2018-05-08 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -317 days 0:45:23

Time elapsed

24:00:00

Time remaining

0:00:00

Problem A
Knapsack

Input

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$.

Output

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