Hide

# Problem BFormúlublað

Image by dolinski
Hannes has a math exam coming up and is only allowed to bring a single sheet of formulas. He needs help deciding what formulas he should put on his sheet. Formula number $i$ takes $l_ i$ lines and its importance is $m_ i$. Hannes wants to know what formulas he should put on the sheet so the sum of the importances is maximized.

## 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


Please log in to submit a solution to this problem