分数: 400 点
问题陈述
该问题的设置与问题G类似,与问题G的不同之处在于最大化的目标和一些约束。
有一家神秘的可乐店。 这家店不直接卖可乐,而是提供空可乐瓶和新瓶装可乐的兑换服务。
最初,高桥有 N 瓶装可乐,从现在开始,他可以选择并执行以下操作之一任意次数(可能为零):
- 喝 1 他有瓶装可乐。他拥有的瓶装可乐数量减少了 1,空瓶数量增加 1。 (如果他在行动前没有瓶装可乐,则不能采取该行动。)
- 选择一个整数 i 之间 1 和 M,包括在内。给予 A_i 空瓶到可乐店,领取 B_i 瓶装可乐和 1 纪念贴纸作为回报。 (他无法选择 i 使得他在行动之前拥有的空瓶数量小于 A_i。 如果没有 i 可以选择,他不能执行此操作。)
高桥喜欢贴纸。当他表现最佳时,他最多可以获得多少张贴纸?
他最初没有空瓶子,也没有贴纸。
约束
- 1\leq N \leq 10^{18}
- 1\leq M \leq 2\times 10^5
- 1\leq B_i < A_i \leq 10^{18}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
输出
将答案输出为整数。
示例输入 1
5 3 5 1 4 3 3 1
示例输出 1
3
考虑以下操作:
- 最初,高桥有 5 瓶装可乐。
- 重复饮酒 1 瓶装可乐 5 次。高桥有 5 空瓶子。
- 进行交流 i=2,给予 4 空瓶换取 3 瓶装可乐和 1 贴纸。高桥有 3 瓶装可乐, 1 空瓶,以及 1 贴纸。
- 重复饮酒 1 瓶装可乐 3 次。高桥有 4 空瓶子和 1 贴纸。
- 进行交流 i=2,给予 4 空瓶换取 3 瓶装可乐和 1 贴纸。高桥有 3 瓶装可乐和 2 贴纸。
- 重复饮酒 1 瓶装可乐 3 次。高桥有 3 空瓶子和 2 贴纸。
- 进行交流 i=3,给予 3 空瓶换取 1 瓶装可乐和 1 贴纸。高桥有 1 瓶装可乐和 3 贴纸。
这些动作完成后,高桥已经 3 贴纸。 无论他如何行动,都无法获得 4 或更多贴纸,所以答案是 3.
示例输入 2
3 3 5 1 5 1 4 2
示例输出 2
0
他只能喝原来的瓶装可乐。
示例输入 3
415 8 327 299 413 396 99 67 108 51 195 98 262 180 250 175 234 187
示例输出 3
11