Contest Duration: - (local time) (150 minutes) Back to Home
B - Bracket Score /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

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

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

### 制約

• 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


### 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