# Problem B

Formúlublað

Languages
en
is
## 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

Group |
Points |
Constraints |

1 |
20 |
$L = 1$ |

2 |
30 |
All formulas have the same importance |

3 |
50 |
No further constraints |

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

4 1 1 2 1 5 1 3 1 7 |
1 7 3 |

Sample Input 2 | Sample Output 2 |
---|---|

4 7 5 2 4 2 2 2 1 2 |
3 6 1 2 3 |

Sample Input 3 | Sample Output 3 |
---|---|

6 10 2 3 1 4 7 10 3 5 4 2 8 12 |
3 17 0 1 2 |