Description

小琪最近迷上了火星，打算给她的朋友们寄一些有火星图案的明信片。网上有n家店铺有这种明信片，各个店铺里这种明信片的价格和库存量都已经知道了。她打算用最少的钱买到这m张明信片，请帮忙计算用多少钱可以买到这m张明信片。

Input

第一行有两个整数m和n。其中m表示要购买的明信片的数量，n表示店铺的个数。
以下n行，每行有两个整数，分别表示某店铺里该种明信片的单价和库存量。

Output

输出仅一个数，表示小琪需要花的最少的钱数。

Sample Input

10 4
4 3
6 2
8 10
3 6

Sample Output

36

HINT

假设店铺数最多不超过1000家。

Source

NBU OJ