题目描述

一个窃贼进入了一个火柴仓库，想尽可能多地偷取火柴。仓库里有 m个集装箱，在第 i 个集装箱里有 ai个火柴盒，每个火柴盒里有 bi火柴。所有的火柴盒都是一样大的。窃贼的背包可以容纳 n火柴盒。你的任务是找出窃贼可以带走的最大数量的火柴。他没有时间重新排列火柴盒中的火柴，这就是为什么他只选择了不超过 n火柴盒，使其中的火柴总量达到最大。

输入格式

输入的第一行包含整数 n(1 ≤ n ≤ 2·10⁸)和整数 m(1 ≤ m ≤ 20).第 i + 1-第1行包含一对数字 a_i和 b_i(1 ≤ a_i ≤ 10⁸, 1 ≤ b_i ≤ 10).所有的输入数字都是整数。

输出格式

输出唯一的数字--问题的答案。

7 3
5 10
2 5
3 6

62

3 3
1 3
2 2
3 1

7