B - Bracket Score Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ．

入力例 1

4
4 2 3 1
2 3 2 4

出力例 1

12

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

入力例 2

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

出力例 2

6629738472

Score : 700 points

Problem Statement

In this problem, we consider strings consisting of (, ), [, and ].

A string x is said to be a good parentheses sequence if and only if one of the following conditions is satisfied:

  • x is an empty sequence.
  • There is a good parentheses sequence s such that concatenating (, s, and ) in this order results in x.
  • There is a good parentheses sequence s such that concatenating [, s, and ] in this order results in x.
  • There are non-empty good parentheses sequences s and t such that concatenating s and t in this order results in x.

For example, [], ([()]), and ()[()] are good parentheses sequences, but neither ()) nor ([)] is a good parentheses sequence.

Given are an even number N and integer sequences A and B of length N each. Here, we define a score for a good parentheses sequence of length N, s=s_1s_2\cdots s_N, as follows:

  • The score for s is the sum of the scores of its characters.
  • The score for the i-th character (1 \leq i \leq N) is A_i if s_i is ( or ), and B_i if s_i is [ or ].

Find the maximum possible score for a good parentheses sequence of length N.

Constraints

  • 2 \leq N \leq 10^5
  • N is an even number.
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

Output

Print the answer.

Sample Input 1

4
4 2 3 1
2 3 2 4

Sample Output 1

12

For s=()[], the score is A_1+A_2+B_3+B_4=12, which is the maximum possible value.

Sample Input 2

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

Sample Output 2

6629738472