AT_abc353_g [ABC353G] Merchant Takahashi

题目描述

在 AtCoder 王国中，有 $N$ 个城镇，分别为城镇 $1$、城镇 $2$、……、城镇 $N$。从城镇 $i$ 移动到城镇 $j$ 需要支付通行费 $C\times|i-j|$ 日元。

作为商人的高桥君，打算参加即将举办的 $M$ 场市场中的 $0$ 场或多场。

第 $i$ 场市场的信息由整数对 $(T_i, P_i)$ 表示，表示第 $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$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6 3
4
5 30
2 10
4 25
2 15

输出 #1

49

输入输出样例 #2

输入 #2

6 1000000000
4
5 30
2 10
4 25
2 15

输出 #2

0

输入输出样例 #3

输入 #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

输入 #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

说明/提示

限制条件

• $1\leq N\leq2\times10^5$
• $1\leq C\leq10^9$
• $1\leq M\leq2\times10^5$
• $1\leq T_i\leq N\ (1\leq i\leq M)$
• $1\leq P_i\leq10^{13}\ (1\leq i\leq M)$
• 输入均为整数

样例解释 1

例如，高桥君可以按如下方式行动，使所持金额增加 $49$ 日元。

• 移动到城镇 $5$。所持金额变为 $10^{10^{100}}-12$ 日元。
• 参加第 $1$ 场市场。所持金额变为 $10^{10^{100}}+18$ 日元。
• 移动到城镇 $4$。所持金额变为 $10^{10^{100}}+15$ 日元。
• 参加第 $3$ 场市场。所持金额变为 $10^{10^{100}}+40$ 日元。
• 移动到城镇 $2$。所持金额变为 $10^{10^{100}}+34$ 日元。
• 参加第 $4$ 场市场。所持金额变为 $10^{10^{100}}+49$ 日元。 无法使所持金额达到 $10^{10^{100}}+50$ 日元或更高，因此输出 49。

样例解释 2

由于通行费过高，高桥君最优选择是不离开城镇 $1$。

样例解释 4

请注意，输出的值可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译