配点 : 100 点
問題文
UT Railway PC 主线是1 沿着书本的思路 有 N+1 站,从始发站到终点站按顺序排列。 它的编号为 0,1,\ldots,N 。每个 i (0\leq i\leq N-1) 关于车站 i 和车站 i+1 彼此相邻,并且这些站之间的拥塞程度为 C_i 。目前该站 附上 0, N 有車両基地。
在下一次时间表修改中,我们将首先通过多次重复以下操作来构建一个仓库。 选择
-
是 i (1\leq i\leq N-1) 并选择电台 将在 i 设立一个车辆仓库。这需要花费 需要 A_i 。
接下来,重复以下操作几次以在车辆段之间运行列车。
-
附有火车站的车站 选择 l,r (l < r) 并在此期间乘坐火车。 1 开始运行。这时,车站 之间 i 和车站 i+1 之间 (l\leq i\lt r) 的拥塞级别为 1 减少。这需要花费 r-l 。
时间表修订的目标是 i (0\leq i\leq N-1) 关于车站 i 和车站 i+1 之间的拥堵程度 0 如下。求建造车站和运营列车所需的最低总成本。
制約
- 输入全部为整数
- 2 \leq N \leq 5\times 10^5
- 1 \leq C_i \leq 10^9 (0\leq i\leq N-1)
- 1 \leq A_i \leq 10^9 (1\leq i\leq N-1)
入力
输入是按以下格式从标准输入给出的。
N
C_0 C_1 \ldots C_{N-1}
A_1 A_2 \ldots A_{N-1}
出力
答案 1 行输出。
入力例 1
4 3 1 4 1 5 9 2
出力例 1
15
駅 3 附有一个火车站,并且车站 0,3 之间的火车 3 本、駅 0,4 之间的火车 1 我们将开始实际操作。那么各站之间的拥塞程度为 0 总成本为 15 。
入力例 2
9 28 35 19 27 84 98 78 79 60 40 35 54 63 72 71 27 94
出力例 2
682