AT_kupc2016_h 壁壁壁壁壁壁壁

[problemUrl]: https://atcoder.jp/contests/kupc2016/tasks/kupc2016_h 京都大学は毎晩西から攻撃してくるゴリラから大学を守るために大学の西側に一直線の壁を築き上げることにした。 また，攻撃が激しい位置は壁だけでは防ぎきれないため，補強材を使って対処している。 補強材の数には限りがあるが，最先端の技術により，次回に攻撃してくるゴリラの数と位置を計算できるので，それに合わせて毎日補強材を移動させている。 その効率化のために，情報学科のエリートであるあなたが呼ばれた。 一直線の壁に沿って補強材を使う位置が等間隔に $ N $ 箇所あり，左から順に $ 1 $，$ 2 $，...，$ N $ の番号が付いている。 前回の攻撃に対する備えで，今，各位置 $ i $ ($ 1\ \leq\ i\ \leq\ N $) には $ A_i $ 個の補強材が使われている。 これらの補強材のうちいくつかを移動させ，各位置 $ i $ ($ 1\ \leq\ i\ \leq\ N $) に $ B_i $ 個以上の補強材が使われている状態にしなければならない。 ただし，位置 $ i $ から位置 $ j $ に補強材を $ 1 $ 個移動させるのにコストが $ |i\ -\ j| $ かかる。 この移動を繰り返し，条件を満たすために要する合計コストの最小値を出力せよ。 また，次々回以降の攻撃のことは考えない。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ ... $ A_N $ $ B_1 $ $ B_2 $ ... $ B_N $

条件を満たすために要する合計コストの最小値を標準出力に1行で出力せよ。 ### 部分点 以下の追加制約を満たすデータセットに正解した場合は $ 30 $ 点の部分点が与えられる。 - $ N\ \leq\ 100 $ - $ A_1\ +\ A_2\ +\ ...\ +\ A_N\ \leq\ 400 $ 以下の追加制約を満たすデータセットに正解した場合は更に $ 30 $ 点の部分点が与えられる。 - $ N\ \leq\ 10^3 $ 追加制約のないデータセットに正解した場合は更に $ 140 $ 点が与えられ，合計で $ 200 $ 点が得られる。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ A_i\ \geq\ 1 $ - $ B_i\ \geq\ 1 $ - $ A_1\ +\ A_2\ +\ ...\ +\ A_N\ \leq\ 10^{12} $ - $ B_1\ +\ B_2\ +\ ...\ +\ B_N\ \leq\ A_1\ +\ A_2\ +\ ...\ +\ A_N $ - 条件を満たす移動方法は必ず存在する ### Sample Explanation 1 位置 $ 2 $ から位置 $ 1 $ へ $ 2 $ 個補強材を移動させる場合の合計コストが最小である。 ### Sample Explanation 3 このケースの入力は部分点の追加制約の1つ目，2つ目の両方を満たす。 ### Sample Explanation 4 このケースの入力は部分点の追加制約の2つ目を満たす。 ### Sample Explanation 5 入力値および出力値は32bit整数型に収まらない場合がある。