Bombo

Gigel este un băiat foarte pofticios. El are acasă $N$ stive, fiecare conţinând câte $M$ cutii cu bomboane. La începutul fiecărei zile, Gigel ia o singură cutie din vârful uneia dintre stive şi mănâncă instantaneu toate bomboanele din ea, după care o aruncă la gunoi (deoarece o cutie cu bomboane fără bomboane în ea îl deprimă). El execută această activitate (de a mânca toate bomboanele din cutia din vârful unei stive) în fiecare zi, până când se golesc toate stivele. Gigel ar fi foarte mulţumit dacă numărul de bomboane din fiecare cutie ar rămâne constant, până când ar ajunge el la cutia respectivă pentru a mânca bomboanele. Realitatea, însă, nu corespunde dorinţelor lui Gigel. Fiecare cutie cu bomboane este caracterizată de doi parametri: $Z$ şi $B$. Iniţial (la începutul primei zile), cutia conţine $Z \cdot B$ bomboane. La sfârşitul fiecărei zile, numărul de bomboane din cutie scade cu $B$. După $Z$ zile, numărul de bomboane din cutie devine $0$. Când numărul de bomboane dintr-o cutie devine $0$, se întâmplă ceva spectaculos: cutia dispare, iar toate cutiile cu bomboabe de deasupra ei, dacă ea nu este, în acel moment, cutia din vârful stivei în care se află, coboară cu o poziţie mai jos în stivă; dacă ea se află în vârful stivei, dar este şi ultima cutie din stivă, atunci stiva se goleşte; dacă ea se află în vârful stivei şi stiva conţine şi alte cutii cu bomboane, atunci cutia de sub ea devine noua cutie din vârful stivei (în cazul în care această cutie dispare şi ea în aceeaşi zi, se consideră cutia de dedesubtul acesteia ş.a.m.d.).

Cerinţă

Cunoscând numărul de stive, numărul de cutii de bomboane din fiecare stivă şi parametrii $Z$ şi $B$ pentru fiecare cutie de bomboane, determinaţi care este numărul maxim total de bomboane pe care le poate mânca Gigel.

Date de intrare

Prima linie a fişierului de intrare bombo.in conţine numerele întregi $N$ şi $M$. Următoarele $N$ linii conţin câte $M$ perechi de numere, descriind cutiile de bomboane din fiecare stivă, de la bază către vârful stivei. O astfel de pereche conţine numerele $Z$ şi $B$, având semnificaţia precizată mai sus. Oricare două numere de pe aceeaşi linie din fişierul de intrare sunt separate printr-un singur spaţiu.

Date de ieșire

În fişierul bombo.out veţi afişa un singur număr, reprezentând numărul maxim de bomboane pe care le poate mânca Gigel.

Restricții și precizări

• $1 \leq a, b \leq 1 \ 000 \ 000$;
• $1 \leq N \leq 4$;
• $1 \leq M \leq 10$;
• Pentru fiecare cutie de bomboane:
  • $1 \leq Z \leq 50$;
  • $1 \leq B \leq 1000000$;
• Cel puţin 30% din fişierele de test vor avea $N \leq 2$
• Cel puţin 65% din fişierele de test vor avea $M \leq 6$
• Cel puţin 55% din fişierele de test vor avea pentru fiecare cutie cu bomboane $Z > N \cdot M$

Exemplul 1

bombo.in

2 3
50 1000 1 3 1 100
2 3000 1 10 1 20

bombo.out

51100

Exemplul 2

bombo.in

4 6
3 1 2 2 3 3 2 4 2 5 2 6
2 1 3 2 2 3 3 4 1 5 3 6
1 1 2 2 2 3 2 4 3 5 1 6
2 1 2 2 3 3 2 4 2 5 2 6

bombo.out

32