一名窃贼进入了火柴仓库,想要偷走尽可能多的火柴。仓库中有m个容器,第i个容器中有ai个火柴盒,每个火柴盒里有bi个火柴。所有火柴盒的大小都相同。窃贼的背包正好可以装n个火柴盒。你的任务是找出窃贼可以带走的最大火柴数量。他没有时间重新排列火柴盒中的火柴,这就是为什么他只选择不超过 n 个火柴盒,以使火柴盒中的火柴总数最大。
输入
输入的第一行包含整数 n (1 ≤ n ≤ 2·108) 和整数 m (1 ≤ m ≤ 20)。第 i + 1 行包含一对数字 ai 和 bi (1 ≤ ai ≤ 108, 1 ≤ bi ≤ 10)。所有输入的数字都是整数。
输出
输出唯一的数字——问题的答案。
示例
输入 #1
7 3 5 10 2 5 3 6
输出 #1
62
输入 #2
3 3 1 3 2 2 3 1
输出 #2
7