有 $2N + 2$ 个座位排成一排。从左起第 $i$ 个座位（$1 \le i \le 2N + 2$）的舒适度为 $A_i$。

共有 $N$ 组两人同行的团体客，以及 2 名单独前来的 VIP 客人，这 $2N + 2$ 名客人需要每人分配一个座位。

但是，不允许将同一个座位分配给两名或以上的客人。

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

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

输入格式

输入从标准输入按以下格式给出：

$N$

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

输出格式

输出一行，表示分配给 2 名 VIP 客人的 2 个座位的舒适度之和的最大值。

限制

• $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 2\,000$。
5. （40 分）无额外限制。

样例数据

样例 1

输入：

2
20 60 40 30 10 50

输出：

90

可以如下分配，使 2 名 VIP 客人的座位舒适度之和为 90：

• 第 1 组团体分配左起第 1、2 个座位。
• 第 2 组团体分配左起第 4、5 个座位。
• 2 名 VIP 客人分配左起第 3、6 个座位。

无法使 2 名 VIP 客人的座位舒适度之和超过 90，因此输出 90。

该输入样例满足子任务 2、3、4、5 的限制。

样例 2

输入：

1
1000000000 1000000000 1 1

输出：

2000000000

该输入样例满足所有子任务的限制。

样例 3

输入：

4
4 10 8 6 7 6 7 8 12 3

输出：

16

该输入样例满足子任务 4、5 的限制。