Score: $550$ points

问题陈述

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$。确定他通过最优选择参加哪些市场以及如何移动，可以获得的最大利润。

形式上，如果他最大化他在$M$个市场之后拥有的金额，那么他最终的金额为$10^{10^{100}} + X$。找出$X$。

以上为大语言模型 kimi 翻译，仅供参考。

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.