← 返回题目列表

Codeforces · 16/B

B. 防盗和火柴

中文机器翻译题面 查看原题

一名窃贼进入了火柴仓库,想要偷走尽可能多的火柴。仓库中有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