分数: 575 点
问题陈述
该问题的设置与问题D类似,与问题D的不同之处在于最大化的目标和一些约束。
有一家神秘的可乐店。 这家店不直接卖可乐,而是提供空可乐瓶和新瓶装可乐的兑换服务。
最初,高桥有 N 瓶装可乐,从现在开始,他可以选择并执行以下操作之一任意次数(可能为零):
- 喝 1 他有瓶装可乐。他拥有的瓶装可乐数量减少了 1,空瓶数量增加 1。 (如果他在行动前没有瓶装可乐,则不能采取该行动。)
- 选择一个整数 i 之间 1 和 M,包括在内。给予 A_i 空瓶到可乐店,领取 B_i 瓶装可乐作为回报。 (他无法选择 i 使得他在行动之前拥有的空瓶数量小于 A_i。 如果没有 i 可以选择,他不能执行此操作。)
高桥喜欢可乐。当他表现最佳时,他最多可以喝多少可乐?
他最初没有空瓶子。
约束
- 1\leq N \leq 10^{15}
- 1\leq M \leq 2\times 10^5
- 1\leq B_i < A_i \leq 300
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
输出
将答案输出为整数。
示例输入 1
5 3 5 4 5 1 4 2
示例输出 1
11
考虑以下操作:
- 最初,高桥有 5 瓶装可乐。
- 重复饮酒 1 瓶装可乐 5 次。高桥有 5 空瓶子。
- 进行交流 i=1,给予 5 空瓶换取 4 瓶装可乐。高桥有 4 瓶装可乐。
- 重复饮酒 1 瓶装可乐 4 次。高桥有 4 空瓶子。
- 进行交流 i=3,给予 4 空瓶换取 2 瓶装可乐。高桥有 2 瓶装可乐。
- 重复饮酒 1 瓶装可乐 2 次。高桥有 2 空瓶子。
至此,高桥一共喝了 5+4+2=11 可乐。 不管他怎么做,他都不能喝酒 12 或更多可乐,所以答案是 11.
示例输入 2
3 3 5 1 4 2 5 1
示例输出 2
3
他只能喝原来的瓶装可乐。
示例输入 3
925532735634776 8 91 40 273 265 286 153 155 126 92 83 291 228 216 90 234 9
示例输出 3
31583804603529464