Hide

Problem L
Formúlublað

/problems/iceland.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 
CPU Time limit 1 second
Memory limit 1024 MB
Languages English, Íslenska
Authors
Hannes Kristján Hannesson and Unnar Freyr Erlendsson
Source Forritunarkeppni Framhaldsskólanna 2018
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in