Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
AtCoder 王国には町 1, 町 2,\ldots, 町 N の N 個の町があります。 町 i から町 j まで移動するには通行料が C\times|i-j| 円かかります。
商人である高橋君は、これから開催される M 回の市場のうち 0 回以上に参加しようと思っています。
i 回目 (1\leq i\leq M) の市場の情報は整数の組 (T _ i,P _ i) で表され、i 回目の市場が町 T _ i で行われ、高橋君が参加すると P _ i 円が得られることを意味します。
すべての 1\leq i\lt M について、i 回目の市場が終了してから i+1 回目の市場が開始します。 高橋君が移動するのにかかる時間は無視できるものとします。
高橋君は、はじめ 10 ^ {10 ^ {100}} 円持っており、町 1 にいます。 参加する市場をうまく選び、うまく移動することによって高橋君が得られる儲けの最大値を求めてください。
厳密には、M 回の市場が終わったあとの所持金を最大化するように高橋君が行動した場合の最終的な高橋君の所持金を 10 ^ {10 ^ {100}}+X として、X を求めてください。
制約
- 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)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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
たとえば、高橋君が次のように行動することで、所持金を 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
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\operatorname{bit} 整数の範囲に収まらない場合があることに注意してください。
Score: 550 points
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.