/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N+1 頂点の無向グラフが与えられます。
頂点には頂点 0 、頂点 1 、\ldots 、頂点 N と名前がついています。
i=1,2,\ldots,N について、頂点 0 と頂点 i を結ぶ重み A_i の無向辺があります。
また、i=1,2,\ldots,N について、頂点 i と頂点 i+1 を結ぶ重み B_i の無向辺があります。(ただし、頂点 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
Score : 500 points
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