UTPC 铁路拥有 $N + 1$ 个车站，沿一条直线排列，从起点站到终点站依次编号为 $0$ 到 $N$。对于每个 $i$ ($0 \le i \le N - 1$)，车站 $i$ 和车站 $i + 1$ 相邻，且这两个车站之间的拥堵程度为 $C_i$。目前，车站 $0$ 和车站 $N$ 处设有“铁路货场”。

在下一次时刻表修订中，将通过多次重复以下操作来建设铁路货场：

• 选择一个车站 $i$ ($1 \le i \le N - 1$) 并在该处建设一个铁路货场。此操作的成本为 $A_i$。

接下来，将通过多次重复以下操作在铁路货场之间运行列车：

• 选择设有铁路货场的车站 $l$ 和 $r$ ($l < r$)，并在这些车站之间运行一列火车。此操作会将车站 $i$ 和 $i + 1$ ($l \le i < r$) 之间的拥堵程度降低 $1$。此操作的成本为 $r - l$。

时刻表修订的目标是将车站 $i$ 和 $i + 1$ ($0 \le i \le N - 1$) 之间的拥堵程度降低到 $0$ 或以下。计算实现此目标所需的建设铁路货场和运行列车的总成本最小值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $C_0$ $C_1$ $\dots$ $C_{N-1}$ $A_1$ $A_1$ $\dots$ $A_{N-1}$

• 输入中的所有值均为整数。
• $2 \le N \le 5 \times 10^5$
• $1 \le C_i \le 10^9$ ($0 \le i \le N - 1$)
• $1 \le A_i \le 10^9$ ($1 \le i \le N - 1$)

输出格式

输出答案。

样例

样例输入 1

4
3 1 4 1
5 9 2

样例输出 1

15

样例输入 2

9
28 35 19 27 84 98 78 79 60
40 35 54 63 72 71 27 94

样例输出 2

682

说明

在第一个样例中，在车站 $3$ 建立了一个铁路货场，在车站 $0$ 和 $3$ 之间设置了 $3$ 列火车，在车站 $0$ 和 $4$ 之间设置了 $1$ 列火车。结果，每个路段的拥堵程度变为 $0$ 或更低，总成本为 $15$。这是最小成本。