Problem C
Köpa Böcker

Du ska köpa $N$ böcker av olika slag (numrerade från $1$ till $N$) och kollar därför runt hos internetbokhandlarna. Varje bok finns hos minst en bokhandel och kan variera i pris mellan de olika bokhandlarna. Dessutom kostar det ett visst belopp i porto att beställa från varje bokhandel, oavsett hur mycket man beställer. Skriv ett program som beräknar det minimala beloppet böckerna kostar dig, inräknat porto. Du kan beställa från hur många bokhandlar som helst.

Indata

Första raden innehåller två tal: $N$, antalet böcker du ska köpa $(1 \le N \le 100$), och $M$, antalet bokhandlar $(1 \le M \le 15)$. Därefter följer en rad med två tal som anger antalet böcker $K$ (av de eftersökta) som finns i första bokhandeln, samt portot för denna bokhandel. Detta följs av $K$ rader innehållande två tal: numret på en bok som finns i bokhandeln och dess pris.

Denna information upprepas sedan för återstående bokhandlar. Alla priser och porton anges i hela kronor, och överstiger inte $10\, 000$. Bokpriser är alltid positiva, medan portot kan vara gratis i vissa butiker.

Utdata

Programmet ska skriva ut det minimala beloppet böckerna kostar, inräknat portokostnaden för alla bokhandlar du beställer från.

Poängsättning

Ditt program kommer testas på 5 testfall. Varje testfall ger dig 20 poäng.

7 4
4 9
1 28
6 45
3 49
4 108
7 49
1 26
2 179
3 54
4 99
5 129
6 45
7 244
5 20
7 249
2 184
5 133
4 109
6 42
1 0
6 43

822