Problem L
Formúlublað

Mynd eftir dolinski

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

4 1
1 2
1 5
1 3
1 7

1 7
3 

4 7
5 2
4 2
2 2
1 2

3 6
1 2 3 

6 10
2 3
1 4
7 10
3 5
4 2
8 12

3 17
0 1 2