问题描述

给定一个具有 $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$ 条边之外，图中没有其他边。

让我们从该图中删除一些边，使得图是二分图。
那么，必须删除的边的权重之和最小是多少？

约束条件

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