Problem Description

There are $2N+2$ seats arranged in a line. The comfort of the $i$-th seat from the left ($1 \le i \le 2N+2$) is $A_i$.

There are $N$ groups of two people who came together, and $2$ VIP guests who came alone. We need to assign one seat to each of these $2N+2$ guests. However, we cannot assign the same seat to two or more guests.

For the two people in the same group, they must be assigned adjacent seats. Under this condition, we want to make the sum of the comforts of the two seats assigned to the two VIP guests as large as possible.

Given the information about the seats, write a program to find the maximum possible sum of the comforts of the two seats assigned to the two VIP guests.

Input Format

The input is given from standard input in the following format.

$N$
$A_1\ A_2\ \cdots\ A_{2N+2}$

Output Format

Print, in one line, the maximum possible sum of the comforts of the two seats assigned to the two VIP guests.

2
20 60 40 30 10 50

90

1
1000000000 1000000000 1 1

2000000000

4
4 10 8 6 7 6 7 8 12 3

16

Hint

Sample Explanation 1

With the following assignment, the sum of the comforts of the VIP guests’ seats can reach $90$.

• Assign seats $1,2$ from the left to group $1$.
• Assign seats $4,5$ from the left to group $2$.
• Assign seats $3,6$ from the left to the two VIP guests.

It is impossible to make the sum of the VIP guests’ seat comforts greater than $90$, so output $90$.

This sample input satisfies the constraints of subtasks $2,3,4,5$.

Constraints

• $1 \le N \le 200\,000$
• $1 \le A_i \le 10^9$ ($1 \le i \le 2N+2$)
• All input values are integers.

Subtasks

1. (10 points) $N = 1$.
2. (10 points) $N \le 2$.
3. (10 points) $N \le 3$.
4. (30 points) $N \le 2000$.
5. (40 points) No additional constraints.

Translated by DeepSeek.

Translated by ChatGPT 5