Hide

Problem L
Formúlublað

Languages en is
/problems/formulublad/file/statement/en/img-0001.jpg
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

Log in