問題文

やきとりくんは、あるリズムゲームで遊んでいました。
このリズムゲームでは、$N$ 個のアクションがあり、$i$ 個目のアクションを正確なタイミングでこなすと $A_i$ 点を獲得することができます。

やきとりくんは、反応が鈍いため、$i$ 個目のアクションでは、正確なタイミングより時刻 $t_i$ だけ遅く反応してしまいました。

さて、このリズムゲームは、すべてのアクションが終わった後に正確なタイミングを調整することができます。
具体的には、非負整数 $x$ を定めて正確なタイミングを $x$ だけ遅らせると、$i$ 個目のアクションにより獲得できる点数は $\max(A_i - |t_i - x| , 0)$となります。

獲得できる点数の合計を最大になるように非負整数 $x$ を決定したときの獲得できる点数の合計を求めてください。

制約

• $1 \leq N \leq 10^{5}$
• $1 \leq A_i \leq 10^{5}$
• $0 \leq t_i \leq 10^{5}$
• 入力はすべて整数である。

入力

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

出力

問題の答えを一行に出力せよ。

入出力例

5
10 15 20 25 30
5 8 1 4 3

91

例えば、$x = 4$ とすると、獲得できる合計の点数は以下のようになります。
$(10 - |5 - 4|) + (15 - |8 - 4|) + (20 - |1 - 4|) + (25 - |4 - 4|) + (30 - |3 - 4|) = 91$ 点

$91$ 点 より多くの点数を獲得することはできないため $91$ と出力します。

4
1 6 38 2357
0 0 0 0

2402

やきとりくんは完璧なタイミングで反応したため、タイミングを調整する必要はありません。