#P16B. Burglar and Matches

    ID: 620 远端评测题 1000ms 64MiB 尝试: 86 已通过: 23 难度: 7 上传者: 标签>greedyimplementationsortings*900待翻译translated机翻

Burglar and Matches

机翻

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

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

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

Description

A burglar got into a matches warehouse and wants to steal as many matches as possible. In the warehouse there are m containers, in the i-th container there are ai matchboxes, and each matchbox contains bi matches. All the matchboxes are of the same size. The burglar's rucksack can hold n matchboxes exactly. Your task is to find out the maximum amount of matches that a burglar can carry away. He has no time to rearrange matches in the matchboxes, that's why he just chooses not more than n matchboxes so that the total amount of matches in them is maximal.

The first line of the input contains integer n (1 ≤ n ≤ 2·108) and integer m (1 ≤ m ≤ 20). The i + 1-th line contains a pair of numbers ai and bi (1 ≤ ai ≤ 108, 1 ≤ bi ≤ 10). All the input numbers are integer.

Output the only number — answer to the problem.

Input

The first line of the input contains integer n (1 ≤ n ≤ 2·108) and integer m (1 ≤ m ≤ 20). The i + 1-th line contains a pair of numbers ai and bi (1 ≤ ai ≤ 108, 1 ≤ bi ≤ 10). All the input numbers are integer.

Output

Output the only number — answer to the problem.

Samples

7 3
5 10
2 5
3 6
62
3 3
1 3
2 2
3 1
7