题目描述

一个窃贼到火柴仓库偷火柴，仓库有 $m$ 个容器，第 $i$ 个容器有 $a_i$ 个火柴盒，其中每个火柴盒中有 $b_i$ 根火柴，窃贼最多可以拿 $n$ 个火柴盒。

输入格式

第一行两个正整数 $n$，$m$。$1 \le n \le 2 \times 10^8$，$1 \le m \le 20$。

下面 $m$ 行每行有两个数 $a_i$ 和 $b_i$，$1 \le a_i \le 10^8$，$1 \le b_i \le 10$。

输出格式

输出窃贼最多能偷多少根火柴。

7 3
5 10
2 5
3 6

62

3 3
1 3
2 2
3 1

7