当前没有测试数据。

F - 使成为二分图

得分 : $500$ points

问题描述

给定一个包含 $N+1$ 个顶点的无向图。
这些顶点被称为顶点 0, 顶点 1, $\ldots$, 顶点 N。

对于每个 $i=1,2,\ldots,N$，图中有一条连接顶点 0 和顶点 i 的边，权重为 $A_i$。

</p>

此外，对于每个 $i=1,2,\ldots,N$，图中有一条连接顶点 i 和顶点 i+1 的边，权重为 $B_i$。 （其中，顶点 N+1 表示顶点 1）。

</p>

该图除了上述的 $2N$ 条边之外没有其它的边。

</p>

让我们从这个图中删除一些边，使得它成为一个二分图。 需要删除的边的总权重最小是多少？

约束条件

• $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