题目描述

小 D 管理着一条水渠。水渠被 $n-1$ 块隔板分成从左到右的 $n$ 个水槽，编号为 $1$ 到 $n$。

每个水槽都是底面积相同、底部等高的长方体。第 $i$ 个水槽的初始水深为 $h_i$。第 $i$ 块隔板位于第 $i$ 个水槽与第 $i+1$ 个水槽之间，拆除它需要花费 $c_i$ 枚金币。

小 D 可以选择一些隔板永久拆除，也可以不拆。拆除完成后，每一段相互连通的水槽中的水会自由流动，最终达到相同水位。未拆除的隔板会阻止两侧的水交换。

水不会流失或溢出，也不能额外加水。最终水深可以不是整数。

请计算：要让全部 $n$ 个水槽的最终水位相同，最少需要花费多少枚金币？

输入格式

第一行一个整数 $n$，表示水槽数量。

第二行 $n$ 个整数 $h_1,h_2,\ldots,h_n$，表示初始水深。

当 $n\ge 2$ 时，第三行包含 $n-1$ 个整数 $c_1,c_2,\ldots,c_{n-1}$，表示各块隔板的拆除费用。当 $n=1$ 时，没有第三行。

输出格式

输出一个整数，表示最少花费的金币数量。

样例

5
1 5 2 4 3
8 2 5 9

13

4
1 1 5 5
2 7 3

12

4
1 2 2 1
6 9 4

10

1
7

0

样例解释

样例 1：拆除第 $1,3$ 块隔板，花费 $8+5=13$。水槽分成 $[1,2]$、$[3,4]$ 和 $[5]$ 三段，各段最终水深都是 $3$。可以证明不存在花费更少的方案。

样例 2：需要拆除全部三块隔板，花费 $2+7+3=12$，最终水深都是 $3$。虽然第 $1,2$ 个水槽初始水深相同，但它们都需要获得右侧的水，二者之间的隔板也必须拆掉。

样例 3：拆除第 $1,3$ 块隔板，花费 $6+4=10$。前两个水槽、后两个水槽分别连通，两段最终水深都是 $1.5$，中间的隔板可以保留。

样例 4：只有一个水槽，已经满足要求，无需花费。

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le h_i\le 10^8$，$1\le c_i\le 10^9$。

金币总数可能超过 32 位整数范围，请使用 long long 存储。