問題

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

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

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

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

入力・制約

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

出力

答えを一行に出力せよ。

入出力例

3
2 3 1
8 7 5

7

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

4
2 1 3 2
1 1 1 1

4

2
12 25
12 25

0

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

4
1234 5678 91011 121314
151617 181920 212223 242526

569049