AT_abc415_g.[ABC415G] Get Many Cola

有一家神奇的可乐商店。这家商店并不直接出售可乐，而是提供用空瓶换新瓶装可乐的服务。

一开始，高桥君拥有 $N$ 瓶瓶装可乐，接下来他可以任意次数（也可以为 $0$ 次）重复以下任意一种操作：

• 喝掉自己拥有的 $1$ 瓶瓶装可乐。瓶装可乐数量减少 $1$，空瓶数量增加 $1$。（如果操作前没有瓶装可乐，则无法进行此操作。）
• 选择一个整数 $i$，满足 $1 \leq i \leq M$。将 $A_i$ 个空瓶交给可乐商店，换取 $B_i$ 瓶瓶装可乐。（如果操作前空瓶数量小于 $A_i$，则无法选择该 $i$。如果没有可选的 $i$，则无法进行此操作。）

高桥君非常喜欢可乐。请问他最多能喝到多少瓶可乐？

注意，高桥君一开始没有任何空瓶。

输入通过标准输入按以下格式给出。

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $A_M$ $B_M$

请输出一个整数，表示最多可以喝到的可乐数量。

限制条件

• $1 \leq N \leq 10^{15}$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq B_i < A_i \leq 300$
• 所有输入均为整数

样例解释 1

考虑如下操作：

• 一开始，高桥君有 $5$ 瓶瓶装可乐。
• 连续 $5$ 次喝掉一瓶可乐，此时高桥君有 $5$ 个空瓶。
• 选择 $i=1$ 进行兑换，用 $5$ 个空瓶换 $4$ 瓶瓶装可乐，此时高桥君有 $4$ 瓶瓶装可乐。
• 连续 $4$ 次喝掉一瓶可乐，此时高桥君有 $4$ 个空瓶。
• 选择 $i=3$ 进行兑换，用 $4$ 个空瓶换 $2$ 瓶瓶装可乐，此时高桥君有 $2$ 瓶瓶装可乐。
• 连续 $2$ 次喝掉一瓶可乐，此时高桥君有 $2$ 个空瓶。

此时高桥君一共喝了 $5+4+2=11$ 瓶可乐。无论如何操作，都无法喝到 $12$ 瓶或更多，因此答案为 $11$。

样例解释 2

只能喝掉最初拥有的瓶装可乐。

由 ChatGPT 4.1 翻译并由人工修缮