问题陈述
沿路有一个村庄。这个村子沿路有 $N$ 个房屋,编号为 $1$ 到 $N$。每栋房屋都有一块田地,最多可种植两个单位的农作物,而只需要一个单位的农作物。将一单位农作物分配给每户家庭的总成本是运输成本和种植成本的总和。
- 搬运成本:在第 $i$ 个房屋和第 $(i+1)$ 个房屋之间搬运一单位农作物的成本为 $d_i$。两个方向的承载成本相同。
- 种植成本:在第 $i$ 个房屋的田地里种植一单位农作物的成本为 $g_i$。
您的任务是计算向每间房屋供应一单位农作物的最低总成本。
输入
输入由单个测试用例组成,格式如下。
$N$ $d_1 \ldots d_{N-1}$ $g_1 \ldots g_N$
第一行由一个整数$N \ (2 \le N \le 200{,}000)$组成,它是房屋的数量。 第二行由 $N-1$ 个整数组成,用空格分隔。第 $i$ 个整数 $d_i \ (1 \le d_i \le 10^9, 1 \le i \le N-1)$ 表示第 $i$ 个房屋与第 $(i+1)$ 个房屋之间的持有成本。 第三行由 $N$ 个整数组成,用空格分隔。第 $i$ 个整数 $g_i \ (1 \le g_i \le 10^9, 1 \le i \le N)$ 表示第 $i$ 个房子的田地的增长成本。
输出
打印向每间房屋供应一单位农作物的最低成本。
示例输入 1
2 3 1 5
样本输入 1 的输出
5
示例输入 2
3 100 100 1 2 3
样本输入 2 的输出
6
示例输入 3
4 1 2 3 1 1 100 100
样本输入 3 的输出
12