Slavenais konditors Mārtiņš Vakariņš ir savācis lielu toršu recepšu kolekciju. Pēdējā laikā Vakariņš ir pamanījis, ka ir grūti atcerēties vai atrast noteiktas tortes recepti, tādēļ ir izveidojis datorsistēmu, kurā ievadījis visas zināmās receptes, katrai no tortēm norādot nepieciešamo izejvielu daudzumu kā $N$ veselu nenegatīvu skaitļu virkni $a_1\ a_2\ \dots\ a_N$. Katram $i$ ($1 \leq i \leq N$) $a_i$ norāda $i$-tās sastāvdaļas daudzumu noteiktās vienībās (piemēram, cukura vai miltu mērvienība būs izteikta gramos, olu dzeltenumi gabalos, utt.). Ja konkrētai receptei attiecīgā sastāvdaļa nav nepieciešama, tad atbilstošā $a_i$ vērtība ir $0$.

Vakariņš vēlas izgatavot pēc iespējas vairāk tortu pēc vienas receptes un zina, cik katra veida izejvielas šobrīd ir noliktavā. Viņš vairākām receptēm vēlas noskaidrot, kādu lielāko daudzumu tortu iespējams izgatavot pēc katras receptes.

Piemēram, ja $N=4$ un izejvielu daudzumi ir tādi, kā norādīts tabulā:

,tad būs iespējams izgatavot vai nu trīs tortes pēc pirmās receptes, vai četras tortes pēc otrās receptes, vai arī vienu torti pēc trešās receptes.

Uzrakstiet programmu, kas dotam izejvielu daudzumam noliktavā un recepšu aprakstiem aprēķina tortu skaitu!

Pirmajā rindā dotas divu naturālu skaitļu $N$ (izejvielu veidu skaits, $N \leq 10^5$) un $R$ (dažādo recepšu skaits, $1 < R \leq 10$) vērtības, kas atdalītas ar tukšumzīmi.

Nākamajā rindā doti $N$ nenegatīvi veseli skaitļi, kur katri divi blakus skaitļi atdalīti ar tukšumzīmi. Katram $i$ ($1 \leq i \leq N$) $i$-tais skaitlis norāda $i$-tās izejvielas daudzumu noliktavā.

Nākamajās $R$ rindās katrā dots vienas tortes receptes apraksts - tortes pagatavošanai nepieciešamais katra veida izejvielu daudzums.

Katrā rindā doti $N$ nenegatīvi veseli skaitļi, kur katri divi blakus skaitļi atdalīti ar tukšumzīmi. Katram $i$ ($1 \leq i \leq N$) $i$-tais skaitlis norāda receptē nepieciešamo $i$-tās izejvielas daudzumu. Zināms, ka katras tortes receptei vismaz vienas izejvielas daudzums ir pozitīvs skaitlis.

Nevienai izejvielai tās daudzums noliktavā vai receptē nepārsniedz $10^9$ vienības.

Izvaddatiem jāsatur tieši $R$ rindas. Katram $r$ ($1 \leq r \leq R$) $r$-tajā rindā jāizvada vesels nenegatīvs skaitlis - lielākais tortu skaits, kādu iespējams izgatavot pēc šīs receptes.