Problem L
Formúlublað

Image by dolinski

Input

The first line of the input contains two integers $1 \leq n \leq 1000$, the number of available formulas, and $1 \leq L \leq 1000$, how many lines fit on the sheet. Then there are $n$ lines, one for each formula, each containing two integers $1 \leq l_i \leq L$ and $0 \leq m_i \leq 10^6$, the number of lines the formula would occupy and its importance.

Output

The first line of the output should contain two integers $k$, the number of chosen formulas, and $M$, the sum of their importances. Then a single line should be printed with $k$ numbers, the indices of the formulas chosen to maximize the sum of their importances.

Scoring

4 1
1 2
1 5
1 3
1 7

1 7
3 

4 7
5 2
4 2
2 2
1 2

3 6
1 2 3 

6 10
2 3
1 4
7 10
3 5
4 2
8 12

3 17
0 1 2