时间限制：1000ms　内存限制：512MB

题目描述

程老师的老同学在山里经营一座货栈，常年囤放山货干货。货栈共有 $n$ 间仓库，沿着一条环山公路排成首尾相接的一圈，编号依次为 $1$ 到 $n$。相邻仓库之间修有搬运通道：第 $1$ 条通道连接 $1$ 号和 $2$ 号仓库，第 $2$ 条连接 $2$ 号和 $3$ 号，依此类推，第 $n$ 条通道连接 $n$ 号和 $1$ 号，正好合上这个圈。山里没有别的路，挑夫搬货只能走这些通道。前阵子盘库，第 $i$ 间仓库存货 $a_i$ 箱，总箱数恰好是 $n$ 的整数倍。

货栈开了十几年，挑夫都是附近村子的熟手，按件计费、当天结算。通道是双向的，一箱货从哪头进哪头出都行，计费只看经过的是哪条通道、过了几次，与方向无关。以前也匀过货，那时各通道工钱差不多，怎么搬都差不了几个钱；今年有几条通道翻修后重新定了价，价差一拉大，搬法就得仔细挑了。

今年老客户改了提货规矩，要求各仓库备货量一致，说是调货单好开。老同学决定把存货匀平：最终每间仓库都恰好囤 $S/n$ 箱（$S$ 为总箱数）。搬货按通道计费：一箱货每经过第 $i$ 条通道一次，付工钱 $w_i$ 元。各通道路况不同，有的平坦有的陡坡，工钱标准各不相同。一箱货经过几条通道就付几条的钱，货在仓库之间倒腾的次数不限，只要最后每间仓库都匀到 $S/n$ 箱。

老同学请程老师把账算清楚：按最省钱的搬法，总工钱最少是多少元。这笔钱不是小数——挑夫按件计酬，搬法定了才好开工。程老师把各间仓库的存货数、各条通道的工钱标准抄在册子上，逐项核对：哪间仓库该出多少货、该进多少货，是定的；可这些货从哪条通道走、绕不绕路，安排不同，总价就大不一样。同一批货顺时针送和逆时针送，价钱能差出好几倍，不能随手一指就完事。

账要算到分毫不差。老同学特意交代，别只给个大概数，将来和挑夫对账，差一块钱都要重新核单子。程老师答应下来，开始算这笔账。

输入格式

第一行一个整数 $n$，表示仓库数量。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每间仓库当前的存货箱数。

第三行 $n$ 个整数 $w_1, w_2, \ldots, w_n$，表示每条通道每箱货经过一次的辛苦钱（第 $i$ 条通道连接 $i$ 号与 $i+1$ 号仓库，第 $n$ 条连接 $n$ 号与 $1$ 号）。

输出格式

输出一行一个整数，表示把货匀平所需的最少搬运费（单位：元）。

数据范围

• 特殊性质 A：所有通道的辛苦钱都相同，即 $w_1 = w_2 = \cdots = w_n$。
• 对于全部数据，$2 \le n \le 10^5$，$0 \le a_i \le 10^5$，$1 \le w_i \le 10^3$，保证 $a_1 + a_2 + \cdots + a_n$ 是 $n$ 的整数倍。

样例

样例 1

输入：

4
8 0 0 4
1 1 1 1

输出：

8

解释：总箱数 $12$，每间仓库要匀到 $3$ 箱。一种搬法：$1$ 号经第 $1$ 条通道送出 $5$ 箱（$3$ 箱留在 $2$ 号，$2$ 箱继续经第 $2$ 条通道送到 $3$ 号），花费 $5 + 2 = 7$ 元；$4$ 号经第 $3$ 条通道送 $1$ 箱给 $3$ 号，花费 $1$ 元。这样 $1$ 号剩 $3$ 箱、$2$ 号有 $3$ 箱、$3$ 号有 $3$ 箱、$4$ 号剩 $3$ 箱，总花费 $8$ 元。试试别的走法，比如让 $1$ 号多绕第 $4$ 条通道，账都不会更省，$8$ 元就是最少的。

样例 2

输入：

4
6 0 0 2
10 1 1 1

输出：

10

解释：总箱数 $8$，每间要匀到 $2$ 箱。第 $1$ 条通道每箱要 $10$ 元，硬闯太贵：从 $1$ 号直接送 $4$ 箱给 $2$ 号就要 $4 \times 10 = 40$ 元。换个方向绕圈走：$1$ 号的 $4$ 箱经第 $4$ 条通道送到 $4$ 号（$4 \times 1 = 4$ 元），$4$ 号凑够自己要的 $2$ 箱后，把多出的 $4$ 箱经第 $3$ 条通道送到 $3$ 号（$4 \times 1 = 4$ 元），$3$ 号留 $2$ 箱，再把剩下 $2$ 箱经第 $2$ 条通道送到 $2$ 号（$2 \times 1 = 2$ 元）。总花费 $4 + 4 + 2 = 10$ 元。绕远路反而便宜，这正是单价闹的。

样例 3

输入：

5
1 2 3 4 5
2 3 1 4 1

输出：

6

解释：总箱数 $15$，每间要匀到 $3$ 箱。一种搬法：$5$ 号多出 $2$ 箱，经第 $5$ 条通道送给 $1$ 号，花费 $2 \times 1 = 2$ 元；$4$ 号多出 $1$ 箱，经第 $3$ 条通道送给 $3$ 号，花费 $1 \times 1 = 1$ 元；$3$ 号把这 $1$ 箱连同中转来的经第 $2$ 条通道送 $1$ 箱给 $2$ 号，花费 $1 \times 3 = 3$ 元。总花费 $2 + 1 + 3 = 6$ 元，这就是最省的搬法。