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 翻译