AT_agc048_b [AGC048B] Bracket Score

[problemUrl]: https://atcoder.jp/contests/agc048/tasks/agc048_b この問題では，`(`,`)`,`[`,`]` からなる文字列を考えます． 文字列 $ 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 $

答えを出力せよ．

### 制約 - $ 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 $ になり，これが最大です．