Fişierul intrare/ieşire:	bombo.in, bombo.out	Sursă	ONI 2006, clasa 10
Autor	Mugurel Ionut Andreica	Adăugată de	Codrea Marcel •marcelcodrea
Timp execuţie pe test	0.05 sec	Limită de memorie	9216 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bombo

Gigel este un baiat foarte pofticios. El are acasa N stive, fiecare continand cate M cutii cu bomboane. La inceputul fiecarei zile, Gigel ia o singura cutie din varful uneia dintre stive si mananca instantaneu toate bomboanele din ea, dupa care o arunca la gunoi (deoarece o cutie cu bomboane fara bomboane in ea il deprima). El executa aceasta activitate (de a manca toate bomboanele din cutia din varful unei stive) in fiecare zi, pana cand se golesc toate stivele. Gigel ar fi foarte multumit daca numarul de bomboane din fiecare cutie ar ramane constant, pana cand ar ajunge el la cutia respectiva pentru a manca bomboanele. Realitatea, insa, nu corespunde dorintelor lui Gigel. Fiecare cutie cu bomboane este caracterizata de doi parametri: Z si B. Initial (la inceputul primei zile), cutia contine Z*B bomboane. La sfarsitul fiecarei zile, numarul de bomboane din cutie scade cu B. Dupa Z zile, numarul de bomboane din cutie devine 0. Cand numarul de bomboane dintr-o cutie devine 0, se intampla ceva spectaculos: cutia dispare, iar toate cutiile cu bomboabe de deasupra ei, daca ea nu este, in acel moment, cutia din varful stivei in care se afla, coboara cu o pozitie mai jos in stiva; daca ea se afla in varful stivei, dar este si ultima cutie din stiva, atunci stiva se goleste; daca ea se afla in varful stivei si stiva contine si alte cutii cu bomboane, atunci cutia de sub ea devine noua cutie din varful stivei (in cazul in care aceasta cutie dispare si ea in aceeasi zi, se considera cutia de dedesubtul acesteia s.a.m.d.).
Cunoscand numarul de stive, numarul de cutii de bomboane din fiecare stiva si parametrii Z si B pentru fiecare cutie de bomboane, determinati care este numarul maxim total de bomboane pe care le poate manca Gigel.

Date de intrare

Prima linie a fisierului de intrare bombo.in contine numerele intregi N si M. Urmatoarele N linii contin cate M perechi de numere, descriind cutiile de bomboane din fiecare stiva, de la baza catre varful stivei. O astfel de pereche contine numerele Z si B, avand semnificatia precizata mai sus. Oricare doua numere de pe aceeasi linie din fisierul de intrare sunt separate printr-un singur spatiu.

Date de iesire

In fisierul bombo.out veti afisa un singur numar, reprezentand numarul maxim de bomboane pe care le poate manca Gigel.

Restrictii si precizari

• 1 ≤ N ≤ 4
• 1 ≤ M ≤ 10
• Pentru fiecare cutie de bomboane: 1 ≤ Z ≤ 50 si 1 ≤ B ≤ 1 000 000.
• Cel putin 30% din fisierele de test vor avea N ≤ 2.
• Cel putin 65% din fisierele de test vor avea M ≤ 6.
• Cel putin 55% din fisierele de test vor avea pentru fiecare cutie cu bomboane Z > N*M.

Exemplu

Cum se trimit solutii?