2808: 窃贼与火柴
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：15
解决：6
题目描述
一个窃贼进入了火柴仓库，想要偷尽可能多的火柴。仓库里有m个集装箱，第i个集装箱里有ai个火柴盒，每个火柴盒里有bi根火柴。所有火柴盒大小相同。窃贼的帆布背包恰能容纳n个火柴盒。你的任务是找出窃贼能拿走的火柴的最大数量。他没时间重新调整火柴盒中的火柴，这就是他只是挑选不超过n个其包含火柴数之和最大的火柴盒的原因。
输入
第一行包含整数n(1<=n<=2*10^8)和整数m(1<=m<=20)。
第i+1行包含一对整数ai和bi(1<=ai<=10^8,1<=bi<=10)。
所有输入的数字都是整数。
输出
唯一一个整数代表问题的答案。
样例输入 复制
【输入样例1】
7 3
5 10
2 5
3 6
【输入样例2】
3 3
1 3
2 2
3 1
样例输出 复制
【输出样例1】
62
【输出样例2】
7