Problem L
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 |
