← 返回题目列表

AtCoder · abc229_f

I. 进行二分

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

分数: 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