問題

クリスマス・イブの日に、santarate君とnumDeer君でプレゼントを分け合いました。そのプレゼントは二人とも同じ NN 種類のプレゼントを渡されており、santarate君には i (1iN)i\ (1\le i\le N) 種類目のプレゼントが AiA_i 個、numDeer君には BiB_i 個だけ分けられていました。

これらのプレゼントについて、クローン能力を使えるsantarate君は正の整数 KK を選んだ後、以下の操作を 00 回以上繰り返すことを考えました。

  • santarate君が持っているプレゼントをいずれか 11 種類だけ選び、能力を使って KK 個だけそのプレゼントを増やすか、KK 個だけ減らす。またはnumDeer君のプレゼントを選んで KK 個だけ増やすか、KK 個だけ減らす。

santarate君は不平等が嫌いな人なので、santarate君とnumDeer君が持っているプレゼントの個数が全種類において等しくなるようにしようと思いました。これを満たす KK を選び、操作を行ったとき、最小で何回の操作で等しくすることができますか?

入力・制約

NN
A1  ANA_1\ …\ A_N
B1  BNB_1\ …\ B_N

1N1051\le N\le 10^5
1Ai,Bi1071\le A_i,B_i\le 10^7
・答えは 101810^{18} 以下に収まることが保証される

出力

答えを一行に出力せよ。

入出力例

入力例1
3
2 3 1
8 7 5
出力例1
7

K=2K=2 を選んだとき、santarate君の持っている 11 種類目のプレゼント A1A_1 に対して操作を 33 回 ( A1+2K=2+2×3=8(=B1)A_1+2K=2+2\times 3=8(=B_1) )、2,32,3 種類目のプレゼント A2,A3A_2,A_3 に対して操作を 22 回ずつ行う (このとき A2+2K=3+2×2=7(=B2),A3+2K=1+2×2=5(=B3)A_2+2K=3+2\times 2=7(=B_2),A_3+2K=1+2\times 2=5(=B_3) となる) ことで、合計 77 回の操作で条件を満たすことができます。 どんな KK を選んでも 66 回以下で条件を満たすことはできないので、77 を出力します。

入力例2
4
2 1 3 2
1 1 1 1
出力例2
4
入力例3
2
12 25
12 25
出力例3
0

最初から条件を満たしていることもあります。

入力例4
4
1234 5678 91011 121314
151617 181920 212223 242526
出力例4
569049

提出


Go (1.21)