通通的工厂生产奶粉需要采购大量的牛奶，因为这是一项利润率很低的业务，所以通通需要将牛奶的价格保持在尽可能低的水平。 现在有几个牛奶提供商，通通可以向他们采购牛奶，每个牛奶提供商的牛奶出售价格（可能）不同。此外，由于奶牛的产奶量是有限的，所以牛奶提供商的出售量也是有限的，每天通通从每个提供商那里购买的牛奶要少于或者等于牛奶提供商的限额。 考虑到通通的牛奶需求量，以及每升牛奶的成本和每个牛奶提供商的可用的牛奶量，计算满足通通的需求所需的最低金额。 注：牛奶提供商每天生产的牛奶总量足以满足通通的需求。

输入描述

第1行：两个整数，N和M。

• 第一个数N（0<=N<=2000000）是通通每天想要的牛奶量。
• 第二个数M（0<=M<=5000）是通通可以向提供商购买的数量。 第2行至第M+1行： 接下来的M行每行分别包含两个整数，Pi和Ai。
• Pi（0<=Pi<=1000）是价格
• Ai(0<=Ai<=2000000）是牛奶提供商每天可以向通通售出的牛奶量。

输出描述

一行一个整数，表示通通可以买到牛奶的最低价格。

输入样例1

100 5
5 20
9 40
3 10
8 80
6 30

输出样例1

630

提示

【数据范围】

• 对于40%的测试数据，N<=100，M<=10。
• 对于70%的测试数据，N<=100000，M<=1000。
• 对于100%的测试数据，N<=2000000，M<=5000。