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