说明

有 $2N+2$ 个座位排成一行。从左数第 $i$ 个座位 ($1 \le i \le 2N+2$) 的舒适度为 $A_i$。

现有 $N$ 组结伴而来的两人团体客人，以及 $2$ 名单身来访的 VIP 客人，需要为这 $2N+2$ 位客人每人分配一个座位。但是，不能将同一个座位分配给两位或以上的客人。

现在，对于属于同一团体的两个人，必须分配相邻的座位。在此条件下，我们希望分配给两位 VIP 客人的两个座位的舒适度之和尽可能大。

给定座位的相关信息，请编写一个程序，求出分配给两位 VIP 客人的两个座位的舒适度之和的最大值。

输入格式

输入以下格式从标准输入给出。

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

输出格式

在标准输出中，以一行输出分配给两位 VIP 客人的两个座位的舒适度之和的最大值。

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

提示

样例解释 1

通过如下分配，两位 VIP 客人的座位舒适度之和可以达到 $90$。

• 为第 1 组团体分配从左数第 $1,2$ 号座位。
• 为第 2 组团体分配从左数第 $4,5$ 号座位。
• 为两位 VIP 客人分配从左数第 $3,6$ 号座位。

无法使两位 VIP 客人的座位舒适度之和大于 $90$，因此输出 $90$。

该输入样例满足子任务 $2,3,4,5$ 的数据范围。

数据范围

• $1 \le N \le 200\,000$
• $1 \le A_i \le 10^9$ ($1 \le i \le 2N+2$)
• 输入的所有值均为整数。

子任务

1. (10 分) $N = 1$
2. (10 分) $N \le 2$
3. (10 分) $N \le 3$
4. (30 分) $N \le 2000$
5. (40 分) 无额外限制。

翻译由 DeepSeek 完成