Hide

Problem B
Formúlublað

Languages en is
/problems/formulublad/file/statement/is/img-0001.jpg
Mynd eftir dolinski
Hannes er að fara í stærðfræðipróf og hann má bara taka með sér eina blaðsíðu af formúlum. Hann vantar hjálp við að ákveða hvaða formúlur hann ætti að setja á formúlublaðið sitt. Formúla númer $i$ tekur $l_i$ línur og mikilvægisgildi hennar er $m_i$. Hannes vill vita hvaða formúlur hann ætti að setja á formúlublaðið sitt þannig að summan af mikilvægisgildum formúlanna á blaðinu sé hámörkuð.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $1 \leq n \leq 1000$, hversu margar formúlur eru og $1 \leq L \leq 1000$, hversu margar línur komast fyrir á blaðinu. Eftir fylgja $n$ línur, ein fyrir hverja formúlu, sem inniheldur tvær heiltölur $1 \leq l_i \leq L$ og $0 \leq m_i \leq 10^6$, fjöldi lína sem formúlan tekur og mikilvægisgildi formúlunnar.

Úttak

Fyrsta línan í úttakinu ætti að innihelda tvær heiltölur $k$, fjölda formúla sem eru valdar og $M$, summuna af mikilvægisgildum þeirra. Síðan kemur ein lína með $k$ tölum, vísunum á formúlunum sem hámarka summuna af mikilvægisgildum.

Stigagjöf

Hópur

Stig

Takmarkanir

1

20

$L = 1$

2

30

Allar formúlur hafa sama mikilvægisgildi

3

50

Engar frekari takmarkanir

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