Perica treba da pređe autom put od grada A do grada B. Njegov auto ima rezervoar zapremine p litara i troši jedan litar goriva na 1 kilometar. Na putu od grada A do grada B se nalaze benzinske pumpe, raspoređene tako da Perica može stići na cilj (znači svake dve uzastopne pumpe su na rastojanju ne većem od p). Cene benzina na pumpama ne moraju biti iste, a predstavljaju cele brojeve između 1 i 1000. Perica želi da pređe put uz minimalni trošak kupujući benzin tamo gde je najjeftiniji, ali tako da može stići na cilj (tj. tako da ne ostane bez benzina negde između neke dve pumpe). Kako je put vrlo dugačak i broj usputnih pumpi velik, on to ne može dovoljno brzo proračunati. Pomozite Perici i napišite program koji će određivati koliko minimalno mora platiti da bi prešao put od A do B.

Ulaz:

Ulazni podaci se nalaze u datoteci put.in. U prvom redu datoteke su dva broja: ceo broj p (1 ≤ p ≤ 100000000 = 10^8) koji prestavlja zapreminu rezervoara i ceo broj s (1 ≤ s ≤ 100000 = 10^5) koji predstavlja broj pumpi na putu. U svakom od sledećih s redova se nalazi opis jedne pumpe i to u redosledu u kome se one nalaze na putu. Opis je zadat sa dva cela broja: broj d (1 ≤ d ≤ p) i to je rastojanje od te pumpe do sledeće (ako je to poslednja pumpa onda je d rastojanje od te pumpe do mesta B) i ceo broj c (1 ≤ c ≤ 1000), cena 1 litra benzina na toj pumpi. Ukupna dužina puta nije veća od 100000000 = 10^8 kilometara. Prva pumpa se nalazi u mestu A.

Izlaz:

U prvom redu datoteke put.out treba ispisati jedan ceo broj koji predstavlja najmanji iznos novca koji treba da plati Perica da bi stigao iz mesta A u mesto B.

Primer:

40 3
10 2
15 1
5 2

40