分数: 550 点
问题陈述
AtCoder王国有 N 城镇: 城镇 1, 2, \ldots, N。 从城镇搬家 i 到镇 j,您必须支付通行费 C \times |i-j| 日元。
商人 Takahashi 正在考虑参与零个或多个 M 即将推出的市场。
的 i第市场 (1 \leq i \leq M) 由一对整数描述 (T_i, P_i),镇上举行集市的地方 T_i 他会赚到 P_i 日元如果他参加的话。
对于所有人 1 \leq i < M, i-第 市场在 (i+1)第-市场开始。 他移动所花费的时间可以忽略不计。
他开始于 10^{10^{100}} 日元,最初在城里 1。 通过最佳选择参与哪些市场以及如何移动来确定他可以获得的最大利润。
正式地,让 10^{10^{100}} + X 是他的最终金额,如果他最大化了他在 M 市场。查找 X.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C \leq 10^9
- 1 \leq M \leq 2 \times 10^5
- 1 \leq T_i \leq N (1 \leq i \leq M)
- 1 \leq P_i \leq 10^{13} (1 \leq i \leq M)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N C M T_1 P_1 T_2 P_2 \vdots T_M P_M
输出
打印答案。
示例输入 1
6 3 4 5 30 2 10 4 25 2 15
示例输出 1
49
例如,高桥可以增加他的钱 49 日元的操作如下:
- 搬到城镇 5。他的钱变成了 10^{10^{100}} - 12 日元。
- 参与第一场市场。他的钱变成了 10^{10^{100}} + 18 日元。
- 搬到城镇 4。他的钱变成了 10^{10^{100}} + 15 日元。
- 参与第三市场。他的钱变成了 10^{10^{100}} + 40 日元。
- 搬到城镇 2。他的钱变成了 10^{10^{100}} + 34 日元。
- 参与第四市场。他的钱变成了 10^{10^{100}} + 49 日元。
不可能将他的钱增加到 10^{10^{100}} + 50 日元或更多,所以打印 49.
示例输入 2
6 1000000000 4 5 30 2 10 4 25 2 15
示例输出 2
0
过路费太高了,他最好不要离开城镇 1.
示例输入 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
请注意,输出值可能超出范围 32位整数。