分数: 500 点
问题陈述
给定一个无向图 N+1 顶点。
顶点称为 Vertex 0,顶点 1, \ldots,顶点 N.
对于每个 i=1,2,\ldots,N,该图有一条无向边,权重为 A_i 连接顶点 0 和顶点 i.
此外,对于每个 i=1,2,\ldots,N,该图有一条无向边,权重为 B_i 连接顶点 i 和顶点 i+1。 (这里,顶点 N+1 代表顶点 1.)
除了这些之外,该图没有其他边 2N 边缘上方。
让我们从该图中删除一些边,以便该图成为二分图。
必须删除的边的最小总权重是多少?
约束
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
输出
打印答案。
示例输入 1
5 31 4 159 2 65 5 5 5 5 10
示例输出 1
16

删除连接顶点的边 0,2 (重量: 4),连接顶点的边 0,4 (重量: 2),以及连接顶点的边 1,5 (重量: 10) 使图成为二分图。
示例输入 2
4 100 100 100 1000000000 1 2 3 4
示例输出 2
10