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.

样例 #1

样例输入 #1

7 3
5 10
2 5
3 6

样例输出 #1

62

样例 #2

样例输入 #2

3 3
1 3
2 2
3 1

样例输出 #2

7