103536: [Atcoder]ABC353 G - Merchant Takahashi

Problem Statement

The Kingdom of AtCoder has $N$ towns: towns $1$, $2$, $\ldots$, $N$. To move from town $i$ to town $j$, you must pay a toll of $C \times |i-j|$ yen.

Takahashi, a merchant, is considering participating in zero or more of $M$ upcoming markets.

The $i$-th market $(1 \leq i \leq M)$ is described by the pair of integers $(T_i, P_i)$, where the market is held in town $T_i$ and he will earn $P_i$ yen if he participates.

For all $1 \leq i < M$, the $i$-th market ends before the $(i+1)$-th market begins. The time it takes for him to move is negligible.

He starts with $10^{10^{100}}$ yen and is initially in town $1$. Determine the maximum profit he can make by optimally choosing which markets to participate in and how to move.

Formally, let $10^{10^{100}} + X$ be his final amount of money if he maximizes the amount of money he has after the $M$ markets. Find $X$.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $C$
$M$
$T_1$ $P_1$
$T_2$ $P_2$
$\vdots$
$T_M$ $P_M$

Output

Print the answer.

Sample Input 1

6 3
4
5 30
2 10
4 25
2 15

Sample Output 1

49

For example, Takahashi can increase his money by $49$ yen by acting as follows:

• Move to town $5$. His money becomes $10^{10^{100}} - 12$ yen.
• Participate in the first market. His money becomes $10^{10^{100}} + 18$ yen.
• Move to town $4$. His money becomes $10^{10^{100}} + 15$ yen.
• Participate in the third market. His money becomes $10^{10^{100}} + 40$ yen.
• Move to town $2$. His money becomes $10^{10^{100}} + 34$ yen.
• Participate in the fourth market. His money becomes $10^{10^{100}} + 49$ yen.

It is impossible to increase his money to $10^{10^{100}} + 50$ yen or more, so print 49.

Sample Input 2

6 1000000000
4
5 30
2 10
4 25
2 15

Sample Output 2

0

The toll fee is so high that it is optimal for him not to move from town $1$.

Sample Input 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

Sample Output 3

5000

Sample Input 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

Sample Output 4

606214471001

Note that the output value may exceed the range of a $32$-bit integer.

问题描述

在AtCoder王国里有$N$个城镇：城镇1，2，$\ldots$，$N$。从城镇$i$移动到城镇$j$，需要支付$C \times |i-j|$日元的通行费。

商人Takahashi正在考虑参加0个或多个即将到来的市场。

第$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$。

约束

• $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

例如，Takahashi可以通过以下方式使他的钱增加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位整数的范围。