/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は N 個の区画からなる一本道の管理者です。区画には左から順に 1 から N までの番号が付けられており、区画 i と区画 i+1（1 \leq i \leq N-1）は互いに隣接しています。
ある日、大雨によっていくつかの区画の路面が陥没してしまいました。陥没後の区画 i の路面の高さは A_i です。
高橋君は道路を整備するために、区画にアスファルトを追加して路面を高くすることにしました。高橋君は以下の操作を好きな回数（0 回でもよい）行うことができます。
- 1 以上 N 以下の整数 i を 1 つ選び、区画 i の路面の高さを 1 だけ増加させる。この操作のコストは C_i である。
同じ区画に対してこの操作を複数回行うこともできます。一方、路面の高さを減少させることはできません。
高橋君の目標は、すべての隣接する区画間で路面の高さの差の絶対値が D 以下になるようにすることです。すなわち、すべての操作が完了した後の区画 i の路面の高さを A_i' としたとき、すべての 1 \leq i \leq N-1 に対して
|A_i' - A_{i+1}'| \leq D
が成り立つようにします。操作の性質上、すべての 1 \leq i \leq N に対して A_i' \geq A_i かつ A_i' は整数です。
この目標を達成するために必要な最小の合計コストを求めてください。
なお、制約の範囲内では目標は必ず達成可能であることが保証されます。
制約
- 1 \leq N \leq 10^6
- 1 \leq D \leq 10^5
- 0 \leq A_i \leq 10^5
- 1 \leq C_i \leq 10^7
- 入力はすべて整数である
入力
N D A_1 A_2 \ldots A_N C_1 C_2 \ldots C_N
- 1 行目には、区画の数を表す整数 N と、隣接する区画の路面の高さの差の上限を表す整数 D が、スペース区切りで与えられる。
- 2 行目には、各区画の陥没後の路面の高さを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 3 行目には、各区画の路面の高さを 1 増加させるコストを表す整数 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
出力
目標を達成するために必要な最小の合計コストを 1 行で出力せよ。
入力例 1
4 2 3 0 5 4 2 3 1 4
出力例 1
9
入力例 2
3 5 1 4 8 10 1 7
出力例 2
0
入力例 3
10 3 8 1 4 12 6 2 15 10 9 3 5 2 8 1 6 4 3 7 2 9
出力例 3
149
入力例 4
30 4 20 3 7 18 25 11 4 30 16 9 2 14 28 6 12 21 5 17 26 8 13 1 19 24 10 15 0 22 27 23 3 15 2 9 6 20 4 1 12 8 17 5 10 14 7 11 13 16 2 19 6 18 3 9 5 12 4 7 10 1
出力例 4
2401
入力例 5
1 100000 0 10000000
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi is the administrator of a straight road consisting of N sections. The sections are numbered 1 to N from left to right, and section i and section i+1 (1 \leq i \leq N-1) are adjacent to each other.
One day, heavy rain caused the road surface in some sections to collapse. The height of the road surface in section i after the collapse is A_i.
To maintain the road, Takahashi decided to add asphalt to the sections to raise the road surface. He can perform the following operation any number of times (possibly zero):
- Choose an integer i between 1 and N (inclusive), and increase the height of the road surface in section i by 1. The cost of this operation is C_i.
He can perform this operation multiple times on the same section. On the other hand, the height of the road surface cannot be decreased.
Takahashi's goal is to make the absolute difference in the height of the road surface between any adjacent sections at most D. That is, if the height of the road surface in section i after all operations are completed is A_i', then for all 1 \leq i \leq N-1:
|A_i' - A_{i+1}'| \leq D
must hold. Due to the nature of the operations, A_i' \geq A_i and A_i' is an integer for all 1 \leq i \leq N.
Find the minimum total cost required to achieve this goal.
Note that under the constraints, it is guaranteed that the goal is always achievable.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq D \leq 10^5
- 0 \leq A_i \leq 10^5
- 1 \leq C_i \leq 10^7
- All input values are integers.
Input
N D A_1 A_2 \ldots A_N C_1 C_2 \ldots C_N
- The first line contains an integer N, representing the number of sections, and an integer D, representing the upper limit of the difference in the height of the road surface between adjacent sections, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N separated by spaces, representing the height of each section's road surface after the collapse.
- The third line contains integers C_1, C_2, \ldots, C_N separated by spaces, representing the cost of increasing the height of each section's road surface by 1.
Output
Print the minimum total cost required to achieve the goal in a single line.
Sample Input 1
4 2 3 0 5 4 2 3 1 4
Sample Output 1
9
Sample Input 2
3 5 1 4 8 10 1 7
Sample Output 2
0
Sample Input 3
10 3 8 1 4 12 6 2 15 10 9 3 5 2 8 1 6 4 3 7 2 9
Sample Output 3
149
Sample Input 4
30 4 20 3 7 18 25 11 4 30 16 9 2 14 28 6 12 21 5 17 26 8 13 1 19 24 10 15 0 22 27 23 3 15 2 9 6 20 4 1 12 8 17 5 10 14 7 11 13 16 2 19 6 18 3 9 5 12 4 7 10 1
Sample Output 4
2401
Sample Input 5
1 100000 0 10000000
Sample Output 5
0