014 - We Used to Sing a Song Together(★3) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3

問題文

AGC 街道には N 人の小学生が住んでおり、小学生 i (1 \leq i \leq N) の家は位置 A_i にあります。
また、小学校は N 校建てられており、小学校 j (1 \leq j \leq N) は位置 B_j にあります。
AGC 街道に住む小学生は性格が悪く、どの人同士も険悪な関係になっているため、全員が別の学校に通うようにしたいです。

また、不便さは次のように定義されます。

  • 小学生 i にとっての家から学校までの距離を E_i とするとき、不便さは距離の総和、すなわち E_1 + E_2 + ... + E_N である。
  • ただし、位置 u から位置 v までの距離は |u-v|

どの生徒も別の学校に通うという条件下における、不便さとして考えられる最小値を求めてください。

制約

  • 1 \leq N \leq 100000
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_j \leq 10^9
  • A_1, A_2, \dots, A_N は相異なる
  • B_1, B_2, \dots, B_N は相異なる
  • 入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

答えを出力してください。


入力例 1

1
869
120

出力例 1

749

小学生 1 の家と小学校 1 の距離は |869 - 120| = 749 です。
この入力では小学生 1 が必ず小学校 1 に通うことになるため、この値が不便さとして考えられる唯一の値であり、最小値です。


入力例 2

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

出力例 2

5

小学生 1,2,3,4,5,6 をそれぞれ小学校 3,2,6,4,5,1 に通わせることにすると、不便さは |8-7|+|6-5|+|9-9|+|1-2|+|2-3|+|0-1|=5 となります。
これ以上不便さを小さくすることはできないため、答えは 5 です。


入力例 3

10
31 41 59 26 53 58 97 93 23 84
17 32 5 8 7 56 88 77 29 35

出力例 3

211

入力例 4

20
804289382 846930886 681692776 714636914 957747792 424238335 719885386 649760491 596516649 189641420 25202361 350490026 783368690 102520058 44897761 967513925 365180539 540383425 304089172 303455735
35005211 521595368 294702567 726956428 336465782 861021530 278722862 233665123 145174065 468703135 101513928 801979801 315634021 635723058 369133068 125898166 59961392 89018454 628175011 656478041

出力例 4

2736647674

Source Name

「競プロ典型90問」14日目