配点 : $700$ 点

問題文

この問題では，(,),[,] からなる文字列を考えます．

文字列 $x$ は，以下のいずれかの条件を満たす時，良い括弧列と呼ばれます．

• $x$ は空文字列である．
• ある良い括弧列 $s$ が存在し，(,$s$,) をこの順に連結すると $x$ が得られる．
• ある良い括弧列 $s$ が存在し，[,$s$,] をこの順に連結すると $x$ が得られる．
• ある空でない良い括弧列 $s$ および $t$ が存在し，$s,t$ をこの順に連結すると $x$ が得られる．

例えば，[], ([()]), ()[()] などは良い括弧列ですが，()), ([)] などは良い括弧列ではありません．

偶数 $N$ と，長さ $N$ の整数列 $A$ および $B$ が与えられます． ここで，長さ $N$ の良い括弧列 $s=s_1s_2\cdots s_N$ に対して，$s$ のスコアを次のように定めます．

• $s$ のスコアは，各文字のスコアの合計である．
• $i$ 文字目 ($1 \leq i \leq N$) のスコアは，$s_i$ が ( または ) ならば $A_i$ であり，$s_i$ が [ または ] ならば $B_i$ である．

長さ $N$ の良い括弧列のスコアとしてあり得る最大の値を求めてください．

制約

• $2 \leq N \leq 10^5$
• $N$ は偶数
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• 入力される数はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$B_1$ $B_2$ $\cdots$ $B_N$

出力

答えを出力せよ．

4
4 2 3 1
2 3 2 4

12

$s=$()[] とするとスコアが $A_1+A_2+B_3+B_4=12$ になり，これが最大です．

10
866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072
178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937

6629738472