← 返回题目列表

AtCoder · utpc2023_o

O. 最佳列车运行

中文机器翻译题面 查看原题

配点 : 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