商人高桥君

题目描述

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

商人高桥君正在考虑参加即将举办的 $M$ 场集市中的任意若干场(也可以一场都不参加)。

第 $i$ 场集市 $(1 \le i \le M)$ 用整数对 $(T_i, P_i)$ 描述:集市在城镇 $T_i$ 举办,若他参加则可以赚取 $P_i$ 日元。

对于所有 $1 \le i \lt 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

例如,高桥君可以通过如下行动使钱增加 $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。

6 1000000000
4
5 30
2 10
4 25
2 15

0

通行费过高,因此最优策略是不从城镇 $1$ 移动。

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 \le N \le 2 \times 10^5$
• $1 \le C \le 10^9$
• $1 \le M \le 2 \times 10^5$
• $1 \le T_i \le N$ $(1 \le i \le M)$
• $1 \le P_i \le 10^{13}$ $(1 \le i \le M)$
• 输入中的所有值均为整数

提示

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