A - Sensor Data Restoration Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は N 個のセンサーが一列に並んだ観測システムを管理しています。各センサーには 1 から N までの番号が付けられており、正常時における i 番目のセンサーの計測値は A_i です。

ある日、機器トラブルにより K 個のセンサーが故障し、計測値が正しく取得できなくなってしまいました。故障したセンサーの番号は B_1, B_2, \ldots, B_K です。これらは昇順とは限りません。

青木君は故障したセンサーのデータを補完するため、各故障センサーに対して推定値を入力しました。故障したセンサー B_j に対して青木君が入力した推定値は C_j です。

補完後の i 番目のセンサーの値を V_i とします。V_i は以下のように定まります。

  • センサー i が故障していない場合（すなわち、i が B_1, B_2, \ldots, B_K のいずれとも等しくない場合）、V_i = A_i
  • センサー i が故障している場合（すなわち、i = B_j となる j が存在する場合）、V_i = C_j

高橋君はシステム全体のデータの滑らかさを評価するため、隣接するセンサー間の値の差の絶対値の総和である「変動量」を計算することにしました。変動量は

\sum_{i=1}^{N-1} |V_{i+1} - V_i|

と定義されます。

変動量を求めてください。

なお、入力では全センサーの正常時の計測値 A_1, A_2, \ldots, A_N が与えられますが、故障したセンサーについては正常時の計測値ではなく推定値が用いられることに注意してください。

制約

  • 2 \leq N \leq 200000
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq N (1 \leq j \leq K)
  • B_1, B_2, \ldots, B_K はすべて異なる
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq K)
  • 入力はすべて整数である

入力

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_K
C_1 C_2 \ldots C_K
  • 1 行目には、センサーの総数を表す整数 N と、故障したセンサーの数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各センサーの正常時の計測値 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • 3 行目には、故障したセンサーの番号 B_1, B_2, \ldots, B_K がスペース区切りで与えられる。
  • 4 行目には、青木君が入力した推定値 C_1, C_2, \ldots, C_K がスペース区切りで与えられる。C_j は故障したセンサー B_j に対応する推定値である。

出力

変動量を 1 行で出力せよ。

入力例 1

5 2
10 20 30 40 50
2 4
25 35

出力例 1

40

入力例 2

4 1
100 200 300 400
3
500

出力例 2

500

入力例 3

10 3
5 12 8 20 15 3 18 7 25 10
3 7 10
10 20 6

出力例 3

103

入力例 4

15 5
1000000000 500000000 300000000 700000000 100000000 900000000 200000000 800000000 400000000 600000000 150000000 850000000 50000000 950000000 250000000
5 2 11 8 14
999999999 1 777777777 123456789 987654321

出力例 4

6078395060

入力例 5

2 2
1 1000000000
2 1
500000000 500000000

出力例 5

0

Score : 266 pts

Problem Statement

Takahashi manages an observation system consisting of N sensors arranged in a row. Each sensor is numbered from 1 to N, and the normal measurement value of the i-th sensor is A_i.

One day, due to an equipment malfunction, K sensors broke down and their measurement values could no longer be correctly obtained. The numbers of the broken sensors are B_1, B_2, \ldots, B_K. These are not necessarily in ascending order.

To fill in the data for the broken sensors, Aoki entered an estimated value for each broken sensor. The estimated value that Aoki entered for broken sensor B_j is C_j.

Let V_i denote the value of the i-th sensor after the data completion. V_i is determined as follows:

  • If sensor i is not broken (i.e., i is not equal to any of B_1, B_2, \ldots, B_K), then V_i = A_i.
  • If sensor i is broken (i.e., there exists a j such that i = B_j), then V_i = C_j.

To evaluate the smoothness of the entire system's data, Takahashi decided to calculate the "total variation," which is the sum of absolute differences between values of adjacent sensors. The total variation is defined as

\sum_{i=1}^{N-1} |V_{i+1} - V_i|

Find the total variation.

Note that while the normal measurement values A_1, A_2, \ldots, A_N of all sensors are given in the input, the estimated values are used instead of the normal measurement values for broken sensors.

Constraints

  • 2 \leq N \leq 200000
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq N (1 \leq j \leq K)
  • B_1, B_2, \ldots, B_K are all distinct
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq K)
  • All input values are integers

Input

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_K
C_1 C_2 \ldots C_K
  • The first line contains two space-separated integers: N, the total number of sensors, and K, the number of broken sensors.
  • The second line contains the normal measurement values A_1, A_2, \ldots, A_N of each sensor, separated by spaces.
  • The third line contains the numbers B_1, B_2, \ldots, B_K of the broken sensors, separated by spaces.
  • The fourth line contains the estimated values C_1, C_2, \ldots, C_K entered by Aoki, separated by spaces. C_j is the estimated value corresponding to broken sensor B_j.

Output

Output the total variation in a single line.

Sample Input 1

5 2
10 20 30 40 50
2 4
25 35

Sample Output 1

40

Sample Input 2

4 1
100 200 300 400
3
500

Sample Output 2

500

Sample Input 3

10 3
5 12 8 20 15 3 18 7 25 10
3 7 10
10 20 6

Sample Output 3

103

Sample Input 4

15 5
1000000000 500000000 300000000 700000000 100000000 900000000 200000000 800000000 400000000 600000000 150000000 850000000 50000000 950000000 250000000
5 2 11 8 14
999999999 1 777777777 123456789 987654321

Sample Output 4

6078395060

Sample Input 5

2 2
1 1000000000
2 1
500000000 500000000

Sample Output 5

0