该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

输入格式

第一行输入一个整数 $n$。

第二行输入 $a_1,a_2,\ldots,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$。

数据范围

对于所有的数据满足：$1 \le n \le 2\times 10^5$，$1 \le a_i \le 10^9$。

• 子任务 1（$10$ 分）：$n = 1$。
• 子任务 2（$10$ 分）：$n \leq 2$。
• 子任务 3（$10$ 分）：$n \leq 3$。
• 子任务 4（$30$ 分）：$n \leq 2000$。
• 子任务 5（$40$ 分）：无特殊限制。