Burglar and Matches

### 题目描述 一个窃贼到火柴仓库偷火柴,仓库有 $m$ 个容器,第 $i$ 个容器有 $a_i$ 个火柴盒,其中每个火柴盒中有 $b_i$ 根火柴,窃贼最多可以拿 $n$ 个火柴盒 。 ### 输入格式 第一行两个正整数 $n$，$m$ 下面 $m$ 行每行有两个数 $a_i$ 和 $b_i$。 ### 输出格式 输出窃贼最多能偷多少根火柴。 ### 说明/提示 #### 数据规模与约定 $ 1 \le n \le 2 \times 10^8$，$1 \le m \le 20$，$1 \le a_i \le 10^8$，$1 \le b_i \le 10$ 。

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.

The first line of the input contains integer $ n $ ( $ 1<=n<=2·10^{8} $ ) and integer $ m $ ( $ 1<=m<=20 $ ). The $ i+1 $ -th line contains a pair of numbers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i}<=10^{8},1<=b_{i}<=10 $ ). All the input numbers are integer.

Output the only number — answer to the problem.

7 3
5 10
2 5
3 6

62

3 3
1 3
2 2
3 1

7