Cūku ferma

Uzdevums

Mirko strādā cūku fermā, kas sastāv no M atsevišķiem aizslēgtiem aizgaldiem. Fermas vadība ne visai uzticas Mirko, tāpēc viņam netiek uzticētas aizgaldu atslēgas.

Fermas vadība ir katrai dienai noteikusi sekojošu cūku pārdošanas kārtību:

Iepriekšējā dienā pirms ierašanās:

• pircējam ir jāpaziņo lielākais cūku skaits cik viņš ir gatavs iegādāties;
• fermas vadība nosaka pircējam ierašanās laiku tā, lai vienlaicīgi fermā atrastos tikai viens prcējs.

Pirkšanas dienā:

• pircējs precīzi noteiktajā laikā vispirms ierodas kantorī un saņem viena vai vairāku aizgaldu atslēgas;
• tad pircējs dodas uz fermu pie Mirko un atslēdz attiecīgos aizgaldus un iegādājas cūkas no šiem atslēgtajiem aizgaldiem. Ja iespējams, pircējs nopērk lielāko pieteikto cūku skaitu. Ja atslēgtajos aizgaldos tik daudz cūku nav, tad pircējs nopērk visas šajos aizgaldos esošās cūkas.
• ja atslēgtajos aizgaldos paliek nenopirktas cūkas, Mirko var tās pārvietot no viena atvērta aizgalda citā. (Katrā aizgaldā var novietot neierobežoti daudz cūku).
• visbeidzot pircējs visus aizgaldus aizslēdz un atslēgas nogādā kantorī.

Katrai dienai Mirko ir zināma pircēju ierašanās kārtība, kuru aizgaldu atslēgas kuram pircējam tiks iedotas un kādu lielāko cūku skaitu katrs pircējs vēlēsies pirkt. Mirko dienas laikā vēlas pārdot lielāko iespējamo cūku skaitu.

Uzrakstiet programmu, kas nosaka, kādu lielāko cūku skaitu dienas laikā Mirko var pārdot!

Ievaddati

Teksta faila pigs.in pirmajā rindā dotas divu naturālu skaitļu M (aizgaldu skaits, 1 ≤M≤1000) un N(pircēju skaits, 1≤N≤100) vērtības, kas atdalītas ar tukšumsimbolu. Aizgaldi ir numurēti ar naturāliem skaitļiem no 1 līdz M, bet pircēji - no 1 līdz N pēc kārtas.

Faila nākošajā rindā dotas M skaitļu vērtības, kas atdalītas ar tukšumsimboliem - cūku skaits katrā aizgaldā. Katrs no šiem skaitļiem ir lielāks vai vienāds ar 0 un nepārsniedz 1000.

Nākošas N faila rindas katra satur informāciju par vienu pircēju (faila i+2-ajā rindā dota informācija par i-to pircēju) formā

A K₁ K₂ .... K_A B

Visi dotie ir veseli skaitļi un nozīmē, ka pircējam būs atslēgas no aizgaldiem ar numuriem K ₁ K₂ .... K_A un pircējs vēlēsies iegādāties ne vairāk kā B cūkas. Skaitļu A un B vērtības var būt 0.

Izvaddati

Teksta faila pigs.out vienīgajā rindā jāizvada vesels skaitlis - lielākais cūku skaits, ko Mirko šajā dienā varēja pārdot.

Piemērs

pigs.in	pigs.out
3 3 3 1 10 2 1 2 2 2 1 3 3 1 2 6	7
pigs.in	pigs.out
6 6 6 3 2 0 1 3 2 1 2 0 1 3 3 1 1 1 2 2 3 8 2 4 5 2 2 4 6 6	15
pigs.in	pigs.out
11 5 1 2 2 1 0 2 4 1 1 1 2 5 1 2 3 4 5 3 4 1 2 6 7 5 2 3 8 1 3 3 6 11 5 3 8 9 10 3	17

Atsauces