Score : $500$ points

问题描述

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

对于每个 $i=1,2,\ldots,N$，图中存在一条权重为 $A_i$ 的无向边，连接 Vertex $0$ 和 Vertex $i$。

另外，对于每个 $i=1,2,\ldots,N$，图中还存在一条权重为 $B_i$ 的无向边，连接 Vertex $i$ 和 Vertex $i+1$。（这里，Vertex $N+1$ 实际上表示 Vertex $1$。）

除了上述这 $2N$ 条边以外，图中没有其他边。

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Given is an undirected graph with $N+1$ vertices.
The vertices are called Vertex $0$, Vertex $1$, $\ldots$, Vertex $N$.

For each $i=1,2,\ldots,N$, the graph has an undirected edge with a weight of $A_i$ connecting Vertex $0$ and Vertex $i$.

Additionally, for each $i=1,2,\ldots,N$, the graph has an undirected edge with a weight of $B_i$ connecting Vertex $i$ and Vertex $i+1$. (Here, Vertex $N+1$ stands for Vertex $1$.)

The graph has no edge other than these $2N$ edges above.

Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?

Constraints

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\dots$ $A_N$

$B_1$ $B_2$ $\dots$ $B_N$

Output

Print the answer.

Sample Input 1

5
31 4 159 2 65
5 5 5 5 10

Sample Output 1

16

Deleting the edge connecting Vertices $0,2$ (weight: $4$), the edge connecting Vertices $0,4$ (weight: $2$), and the edge connecting Vertices $1,5$ (weight: $10$) makes the graph bipartite.

Sample Input 2

4
100 100 100 1000000000
1 2 3 4

Sample Output 2

10

update @ 2024/3/10 10:01:45