Заради бранот поскапувања на цените Владата на РМ одлучи да интервенира на пазарот за пченица. За таа цел таа треба да откупи одредено количество на пченица од дадена листа на производители.

Секој производител има одредено количество пченица, и секој може да ја нуди истата за различна цена по килограм. Владата може да одлучи да го купи целото количество пченица од производителот или само одреден дел.

За дадени информации за побарувањето на Владата, бројот на производители, како и за понудата на секој производител, да се пресмета минималната сума пари која е потребна за да се обезбеди побаруваната количина.

Влез

Во првата линија од влезот се дадени два цели броја N и M, каде N (1 <= N <= 2000000) е количеството пченица кое владата треба да го откупи, додека M (1 <= M <= 5000) е бројот на производители од кои може да купува.

Следните М линии содржат по два цели броја Ci и Ki, каде Ci (1 <= Ci <= 1000) е цената во денари (по килограм) која ја наплаќа i-тиот производител, а Ki (1 <= Ki <= 2000000) е количеството на пченица (во килограми) кое i-тиот производител го нуди.

Излез

Во единствената линија се запишува еден цел број: минималната сума потребна за да се откупи бараната количина. Секогаш ќе има начин да се задоволат потребите и да се откупи бараната количина пченица.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
100 5
5 20
9 40
3 10
7 80
6 30

излез
590

Објаснување: 30 (3*10) + 100 (5*20) + 180 (6*30) + 280 (7*40) = 590