CF16B.Burglar and Matches

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 a__i matchboxes, and each matchbox contains b__i 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.

一名窃贼闯入了一座火柴仓库，想要尽可能多地偷走火柴。仓库中共有 $m$ 个容器，第 $i$ 个容器中有 $a_i$ 个火柴盒，每个火柴盒中含有 $b_i$ 根火柴。所有火柴盒大小相同。窃贼的背包恰好能装下 $n$ 个火柴盒。你的任务是计算出该窃贼最多能带走多少根火柴。他没有时间重新分配火柴盒中的火柴，因此他只能选择至多 $n$ 个火柴盒，使得其中所含火柴总数最大。

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 a__i and b__i (1 ≤ a__i ≤ 108, 1 ≤ b__i ≤ 10). All the input numbers are integer.

输入的第一行包含整数 $n$（$1 ≤ n ≤ 2·10^8$）和整数 $m$（$1 ≤ m ≤ 20$）。第 $i+1$ 行包含一对数字 $a_i$ 和 $b_i$（$1 ≤ a_i ≤ 10^8$，$1 ≤ b_i ≤ 10$）。所有输入的数字均为整数。

Output the only number — answer to the problem.

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