F - Narrow Passage 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

N 人の人が数直線上に立っています。人にはそれぞれ 1, 2, \ldots, N の番号が付けられており、はじめ人 i は座標 S_i にいます。ただし、S_i はそれぞれ相異なります。

あなたは、以下の操作を繰り返し行うことができます。

  • 人を 1 人選ぶ。その人が現在いる座標を x としたとき、x - 1 または x + 1 に移動させる。ただし、移動先に人がいる場合は、移動先にいる人を同時に座標 x に移動させる。

各人 i が座標 T_i にいる状態になるまでの操作回数として考えられる最小値を求めてください。ただし、T_i はそれぞれ相異なります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq S_i, T_i \leq 10^9
  • i \neq j のとき S_i \neq S_j かつ T_i \neq T_j
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

出力

答えを出力せよ。

入力例 1

3
4 2 5
3 4 1

出力例 1

6

はじめ、人 1, 2, 3 はそれぞれ座標 4, 2, 5 にいます。以下のように操作を行うことで、6 回の操作で人 1, 2, 3 がそれぞれ座標 3, 4, 1 にいるようになります。

  • 人 1 を座標 4 から 3 に移動させる。この操作を行った後、人 1, 2, 3 はそれぞれ座標 3, 2, 5 にいる。

  • 人 1 を座標 3 から 2 に移動させる。座標 2 には人 2 がいるため、人 2 は同時に座標 3 に移動する。この操作を行った後、人 1, 2, 3 はそれぞれ座標 2, 3, 5 にいる。

  • 人 3 を座標 5 から 4 に移動させる。この操作を行った後、人 1, 2, 3 はそれぞれ座標 2, 3, 4 にいる。

  • 人 3 を座標 4 から 3 に移動させる。座標 3 には人 2 がいるため、人 2 は同時に座標 4 に移動する。この操作を行った後、人 1, 2, 3 はそれぞれ座標 2, 4, 3 にいる。

  • 人 3 を座標 3 から 2 に移動させる。座標 2 には人 1 がいるため、人 1 は同時に座標 3 に移動する。この操作を行った後、人 1, 2, 3 はそれぞれ座標 3, 4, 2 にいる。

  • 人 3 を座標 2 から 1 に移動させる。この操作を行った後、人 1, 2, 3 はそれぞれ座標 3, 4, 1 にいる。

入力例 2

4
2 4 5 9
2 4 5 1

出力例 2

11

入力例 3

6
5 2 9 1 6 8
1 4 7 0 9 3

出力例 3

13

Score : 500 points

Problem Statement

There are N people standing on a number line. The people are numbered 1, 2, \ldots, N, and initially person i is at coordinate S_i. Here, the S_i are pairwise distinct.

You can repeatedly perform the following operation.

  • Choose one person. Let x be the coordinate where that person currently is, and move them to x - 1 or x + 1. If there is a person at the destination, that person is simultaneously moved to coordinate x.

Find the minimum number of operations required to reach a state where each person i is at coordinate T_i. Here, the T_i are pairwise distinct.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq S_i, T_i \leq 10^9
  • S_i \neq S_j and T_i \neq T_j if i \neq j.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

Output

Output the answer.

Sample Input 1

3
4 2 5
3 4 1

Sample Output 1

6

Initially, persons 1, 2, 3 are at coordinates 4, 2, 5, respectively. By performing the operations as follows, persons 1, 2, 3 end up at coordinates 3, 4, 1, respectively, in six operations.

  • Move person 1 from coordinate 4 to 3. After this operation, persons 1, 2, 3 are at coordinates 3, 2, 5, respectively.

  • Move person 1 from coordinate 3 to 2. Since person 2 is at coordinate 2, person 2 simultaneously moves to coordinate 3. After this operation, persons 1, 2, 3 are at coordinates 2, 3, 5, respectively.

  • Move person 3 from coordinate 5 to 4. After this operation, persons 1, 2, 3 are at coordinates 2, 3, 4, respectively.

  • Move person 3 from coordinate 4 to 3. Since person 2 is at coordinate 3, person 2 simultaneously moves to coordinate 4. After this operation, persons 1, 2, 3 are at coordinates 2, 4, 3, respectively.

  • Move person 3 from coordinate 3 to 2. Since person 1 is at coordinate 2, person 1 simultaneously moves to coordinate 3. After this operation, persons 1, 2, 3 are at coordinates 3, 4, 2, respectively.

  • Move person 3 from coordinate 2 to 1. After this operation, persons 1, 2, 3 are at coordinates 3, 4, 1, respectively.

Sample Input 2

4
2 4 5 9
2 4 5 1

Sample Output 2

11

Sample Input 3

6
5 2 9 1 6 8
1 4 7 0 9 3

Sample Output 3

13