题目描述

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

文字列 $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$ の良い括弧列のスコアとしてあり得る最大の値を求めてください．

输入格式

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

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

输出格式

答えを出力せよ．

题目大意

我们定义好串如下：

• 空串是好串

• 如果 S 为好串，那么 ( +S+ ) 为好串。

• 如果 S 为好串，那么 [ +S+ ] 为好串。

• 如果 S 和 T 均为好串，那么 S+T 为好串。

现在给定长度为偶数的两个序列 $A$ 和 $B$。

我们定义一个好串 $S$ 的分数如下：

• 如果 $S_i=$ ( 或 $S_i=$ )，那么第 $i$ 位贡献的分数为 $A_i$。

• 如果 $S_i=$ [ 或 $S_i=$ ]，那么第 $i$ 位贡献的分数为 $B_i$。

求 $S$ 可能的最大分数是多少。

4
4 2 3 1
2 3 2 4

12

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

6629738472

提示

制約

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

Sample Explanation 1

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