Merchant Takahashi

题目描述

AtCoder 王国有 $N$ 个城镇：城镇 $1$、$2$、……、$N$。 从城镇 $i$ 移动到城镇 $j$，你必须支付通行费 $C \times |i-j|$ 日元。 商人高桥正在考虑参加 $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$。 确定通过最优选择参加哪些集市以及如何移动他能获得的最大利润。 形式化地，若他在使得他在 $M$ 个集市之后拥有的金额最大化的情况下最终拥有 $10^{10^{100}} + X$ 日元，求 $X$。

输入格式

输入由标准输入按以下格式给出： $N$ $C$ $M$ $T_1$ $P_1$ $T_2$ $P_2$ $\vdots$ $T_M$ $P_M$

输出格式

输出答案。

6 3
4
5 30
2 10
4 25
2 15

49

6 1000000000
4
5 30
2 10
4 25
2 15

0

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

5000

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

606214471001

提示

$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)$ 所有输入值均为整数。例如，高桥可以通过如下操作将他的钱增加 $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$。
通行费非常高，以至于不移动离开城镇 $1$ 是最优的。
注意输出值可能超过 32 位整数的范围。

标签: AtCoder|abc353G

来源

AtCoder|abc353G