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 ≤ i ≤ N) trebuie să producă în fiecare zi de muncă pi potcoave, iar fiecare a ki-a zi va fi liberă (adică muncitorul i va fi liber în ziua ki, 2ki, 3ki, …). În ziua liberă el nu va veni la atelier, deci nu produce potcoave. Atelierul tocmai a primit o comandă de M potcoave.

Cerința

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 pi ki, cu semnificaţia din enunţ (1 ≤ i ≤ 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 ≤ M ≤ 1018
• 1 ≤ N ≤ 10.000
• 1 ≤ pi ≤ 1018 (1 ≤ i ≤ N)
• 2 ≤ ki ≤ 1018 (1 ≤ i ≤ N)

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.