AT_abc415_d.[ABC415D] Get Many Stickers

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

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

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

高桥君非常喜欢贴纸。请问他最多能获得多少张贴纸？

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

输入通过标准输入给出，格式如下：

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

请输出一个整数，表示最多可以获得的贴纸数量。

限制条件

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

样例解释 1

可以考虑如下操作：

• 最初，高桥君有 $5$ 瓶瓶装可乐。
• 连续 $5$ 次喝掉 $1$ 瓶瓶装可乐。此时高桥君有 $5$ 个空瓶。
• 选择 $i=2$ 进行兑换，用 $4$ 个空瓶换 $3$ 瓶瓶装可乐和 $1$ 张贴纸。此时高桥君有 $3$ 瓶瓶装可乐、$1$ 个空瓶、$1$ 张贴纸。
• 连续 $3$ 次喝掉 $1$ 瓶瓶装可乐。此时高桥君有 $4$ 个空瓶、$1$ 张贴纸。
• 选择 $i=2$ 进行兑换，用 $4$ 个空瓶换 $3$ 瓶瓶装可乐和 $1$ 张贴纸。此时高桥君有 $3$ 瓶瓶装可乐、$2$ 张贴纸。
• 连续 $3$ 次喝掉 $1$ 瓶瓶装可乐。此时高桥君有 $3$ 个空瓶、$2$ 张贴纸。
• 选择 $i=3$ 进行兑换，用 $3$ 个空瓶换 $1$ 瓶瓶装可乐和 $1$ 张贴纸。此时高桥君有 $1$ 瓶瓶装可乐、$3$ 张贴纸。

上述操作结束后，高桥君共获得 $3$ 张贴纸。无论如何操作，都无法获得 $4$ 张或更多贴纸，因此答案为 $3$。

样例解释 2

只能喝掉原本拥有的瓶装可乐。

由 ChatGPT 4.1 翻译