化为二分图

题目描述

给定一个具有 $N+1$ 个顶点的无向图。

顶点分别称为顶点 $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$ 条边外,图中没有其他边。

从该图中删除一些边,使得图成为二分图。

求需要删除的边的最小总权重。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

输出格式

输出答案。

样例

5
31 4 159 2 65
5 5 5 5 10

16

删除连接顶点 $0,2$ 的边(权重 $4$)、连接顶点 $0,4$ 的边(权重 $2$)和连接顶点 $1,5$ 的边(权重 $10$),可以使图成为二分图。

4
100 100 100 1000000000
1 2 3 4

10

数据范围

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• 输入中的所有值均为整数