potcoave

La atelierul de făcut potcoave lucrează $N$ muncitori, numerotaţi pentru simplitate de la $1$ la $N$. Fiecare muncitor a încheiat la angajare un contract în care este specificat numărul de potcoave pe care trebuie să le producă muncitorul în fiecare zi de muncă, respectiv a câta zi muncitorul este liber. Mai exact, muncitorul $i$ ($1 \leq i \leq N$) trebuie să producă în fiecare zi de muncă $p_i$ potcoave, iar fiecare a $k_i$-a zi va fi liberă (adică muncitorul $i$ va fi liber în ziua $k_i$, $2k_i$, $3k_i$, ...). În ziua liberă el nu va veni la atelier, deci nu produce potcoave. Atelierul tocmai a primit o comandă de $M$ potcoave.

Cerinţă

Scrieţi un program care să determine numărul minim de zile după care comanda poate fi integral livrată.

Date de intrare

Fişierul de intrare potcoave.in conţine pe prima linie numărul natural $M$ reprezentând numărul de potcoave care trebuie să fie livrate. Pe cea de a doua linie se află numărul natural $N$ reprezentând numărul de muncitori. Pe următoarele $N$ linii sunt scrise datele contractuale ale celor $N$ muncitori. Pe a $i$-a linie dintre cele $N$ se află două numere naturale separate prin spaţiu $p_i \ k_i$, cu semnificaţia din enunţ ($1 \leq i \leq N$).

Date de ieşire

Fişierul de ieşire potcoave.out va conţine o singură linie pe care va fi scris numărul minim de zile după pot fi livrate cele $M$ potcoave din comanda primită.

Restricţii şi precizări

• $1 \leq M \leq 10^{18}$
• $1 \leq N \leq 10^{4}$
• $1 \leq p_i \leq 10^{18}$, pentru $1 \leq i \leq N$
• $2 \leq k_i \leq 10^{18}$, pentru $1 \leq i \leq N$
• Pentru $10$ puncte, $N=1$.
• Pentru alte $16$ puncte, $1 < N \leq 10$ și $M \leq 100 \ 000$.
• Pentru alte $18$ puncte, $N=2$ și $M>100 \ 000$.

Exemplu

potcoave.in

100
3
2 3
3 4
5 7

potcoave.out

13

Explicație

Ziua $1$: lucrează toţi cei $3$ muncitori şi produc $2+3+5=10$ potcoave.
Ziua $2$: lucrează toţi cei $3$ muncitori şi produc $2+3+5=10$ potcoave.
Ziua $3$: lucrează muncitorii $2$ şi $3$ şi produc $3+5=8$ potcoave.
Ziua $4$: lucrează muncitorii $1$ şi $3$ şi produc $2+5=7$ potcoave.
Ziua $5$: lucrează toţi cei $3$ muncitori şi produc $2+3+5=10$ potcoave.
Ziua $6$: lucrează muncitorii $2$ şi $3$ şi produc $3+5=8$ potcoave.
Ziua $7$: lucrează muncitorii $1$ şi $2$ şi produc $2+3=5$ potcoave.
Ziua $8$: lucrează muncitorii $1$ şi $3$ şi produc $2+5=7$ potcoave.
Ziua $9$: lucrează muncitorii $2$ şi $3$ şi produc $3+5=8$ potcoave.
Ziua $10$: lucrează toţi cei $3$ muncitori şi produc $2+3+5=10$ potcoave.
Ziua $11$: lucrează toţi cei $3$ muncitori şi produc $2+3+5=10$ potcoave.
Ziua $12$: lucrează doar muncitorul $3$ şi produce $5$ potcoave.
Ziua $13$: lucrează toţi cei $3$ muncitori şi produc $2+3+5=10$ potcoave.
După $13$ zile numărul total de potcoave produse este $10+10+8+7+10+8+5+7+8+10+10+5+10=108$, suficient pentru a onora comanda.