[ABC353] G - Merchant Takahashi

G - Merchant Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 分

题面

AtCoder 王国有 个城镇: 城镇 , , , 。从城镇 移动到城镇 ，需要支付 日元的通行费。

一位名叫高桥的商人正在考虑参加零个或多个即将举办的 个市场。

第 个市场 () 描述为整数对 ，表示该市场将在城镇 举行，如果他参加则可以赚取 日元。

对于所有 ，第 个市场结束于第 个市场开始之前。他的移动时间可以忽略不计。

他初始持有 日元，并最大化选择参加哪些市场以及如何移动来确定他可以获得的最大利润。

具体来说，如果他在 个市场后最大化了他的金额，设 为他最终的金额，求 。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入获得如下格式的输入：

输出

输出答案。

---

输入样例 1

6 3
4
5 30
2 10
4 25
2 15

输出样例 1

49

例如，高桥可以通过以下方式增加他的金额 日元：

• 移动到城镇 。他的金额变为 日元。
• 参加第一个市场。他的金额变为 日元。
• 移动到城镇 。他的金额变为 日元。
• 参加第三个市场。他的金额变为 日元。
• 移动到城镇 。他的金额变为 日元。
• 参加第四个市场。他的金额变为 日元。

无法使他的金额达到 日元或更多，因此输出 49。

---

输入样例 2

6 1000000000
4
5 30
2 10
4 25
2 15

输出样例 2

0

通行费太高，最佳策略是他不从城镇 移动。

---

输入样例 3

50 10
15
37 261
28 404
49 582
19 573
18 633
3 332
31 213
30 377
50 783
17 798
4 561
41 871
15 525
16 444
26 453

输出样例 3

5000

---

输入样例 4

50 1000000000
15
30 60541209756
48 49238708511
1 73787345006
24 47221018887
9 20218773368
34 40025202486
14 28286410866
24 82115648680
37 62913240066
14 92020110916
24 20965327730
32 67598565422
39 79828753874
40 52778306283
40 67894622518

输出样例 4

606214471001

注意输出值可能超出 位整数的范围。