/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は車で高速道路を走って目的地まで向かうことになりました。
この高速道路には、入口から目的地へ向かう途中に N 個の料金所が順番に設置されています。i 番目の料金所は入口から距離 D_i メートルの位置にあります。目的地は入口から距離 G メートルの位置にあり、すべての料金所よりも入口から遠い場所にあります。
高橋君の車は常に毎秒 1 メートルの一定速度で走行します。料金所に到達すると停止して料金を支払う必要があり、i 番目の料金所では停止してから支払いを完了し再出発するまでに T_i 秒かかります。料金所以外で停止することはありません。
高橋君は ETC カードを持っており、利用区間を 必ずちょうど1つ 設定しなければなりません。具体的には、ある整数 i（1 \leq i \leq N-K+1）を選び、i 番目から i+K-1 番目までの番号が連続する ちょうど K 個 の料金所を ETC 利用区間として指定します。ETC 利用区間に指定された K 個の料金所では停止せずにそのまま通過でき、支払い時間はかかりません。それ以外の料金所では通常どおり停止して支払いを行います。
高橋君が高速道路の入口を出発してから目的地に到達するまでにかかる時間は、走行時間（入口から目的地までの距離が G メートル、速度が毎秒 1 メートルであるため G 秒）に、ETC 利用区間以外の各料金所での支払い時間の合計を加えたものです。ETC 利用区間の選び方を最適にしたとき、この所要時間の最小値を求めてください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq G \leq 10^9
- 1 \leq D_i < G (1 \leq i \leq N)
- D_1 < D_2 < \cdots < D_N
- 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N K G D_1 T_1 D_2 T_2 \vdots D_N T_N
- 1 行目には、料金所の数を表す整数 N、ETC 利用区間として指定する料金所の数を表す整数 K、入口から目的地までの距離を表す整数 G が、スペース区切りで与えられる。
- 1 + i 行目（1 \leq i \leq N）には、i 番目の料金所の入口からの距離 D_i と、その料金所での支払いにかかる時間 T_i が、スペース区切りで与えられる。
出力
高橋君が高速道路の入口から目的地まで到達するのにかかる最短時間を 1 行で出力せよ。
入力例 1
3 2 100 10 5 30 10 60 3
出力例 1
103
入力例 2
5 3 1000 100 20 200 50 400 30 600 40 800 10
出力例 2
1030
入力例 3
7 4 500000000 1000 100000000 50000 200000000 100000 150000000 200000 300000000 300000 50000000 400000 250000000 450000 100000000
出力例 3
900000000
Score : 333 pts
Problem Statement
Takahashi is driving on a highway to reach his destination.
Along this highway, there are N toll booths placed in order between the entrance and the destination. The i-th toll booth is located at a distance of D_i meters from the entrance. The destination is located at a distance of G meters from the entrance, and it is farther from the entrance than all toll booths.
Takahashi's car always travels at a constant speed of 1 meter per second. When he reaches a toll booth, he must stop and pay the toll; at the i-th toll booth, it takes T_i seconds from stopping to completing the payment and departing again. He does not stop anywhere other than at toll booths.
Takahashi has an ETC card and must set exactly one ETC usage section. Specifically, he chooses an integer i (1 \leq i \leq N-K+1) and designates exactly K consecutively numbered toll booths from the i-th to the (i+K-1)-th as the ETC usage section. At the K toll booths designated as the ETC usage section, he can pass through without stopping, incurring no payment time. At all other toll booths, he stops and pays as usual.
The time it takes for Takahashi to travel from the highway entrance to the destination is the sum of the travel time (since the distance from the entrance to the destination is G meters and the speed is 1 meter per second, this is G seconds) and the total payment time at all toll booths outside the ETC usage section. Find the minimum possible total time when the ETC usage section is chosen optimally.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq G \leq 10^9
- 1 \leq D_i < G (1 \leq i \leq N)
- D_1 < D_2 < \cdots < D_N
- 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N K G D_1 T_1 D_2 T_2 \vdots D_N T_N
- The first line contains three space-separated integers: N, the number of toll booths; K, the number of toll booths to designate as the ETC usage section; and G, the distance from the entrance to the destination.
- The (1 + i)-th line (1 \leq i \leq N) contains two space-separated values: D_i, the distance of the i-th toll booth from the entrance, and T_i, the time required for payment at that toll booth.
Output
Output in a single line the minimum time it takes for Takahashi to travel from the highway entrance to the destination.
Sample Input 1
3 2 100 10 5 30 10 60 3
Sample Output 1
103
Sample Input 2
5 3 1000 100 20 200 50 400 30 600 40 800 10
Sample Output 2
1030
Sample Input 3
7 4 500000000 1000 100000000 50000 200000000 100000 150000000 200000 300000000 300000 50000000 400000 250000000 450000 100000000
Sample Output 3
900000000