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

Problem BFormúlublað

Inntak

Úttak

Stigagjöf

Problem B
Formúlublað