题目描述

社团团建活动准备了一整块环形披萨，它被均匀切分成了$3n$块尺寸各不相同的扇形小块，大家约定了一套固定的轮流选取规则来分完所有披萨，小珅作为先手发起选取，小泽和另一位伙伴分别按照规则跟进挑选，小珅需要规划初始选取方案，让自己最终拿到的披萨总尺寸尽可能大，请你帮他算出能取得的最大总和。

披萨的小块沿顺时针排布，尺寸由数组$a_i$依次给出，完整选取规则如下：

1. 小珅先任意挑选一块未被取走的披萨；
2. 小泽选取小珅刚选的那块逆时针相邻的剩余披萨；
3. 另一位伙伴选取小珅刚选的那块顺时针相邻的剩余披萨；
4. 重复以上三轮选取的流程，直到所有披萨全部分配完毕。

请求出小珅通过最优初始选择与后续策略，能够获得的披萨尺寸总和的最大值。

输入格式

第一行输入一个正整数$n$； 第二行输入$3n$个正整数$a_1,a_2,\dots,a_{3n}$，按顺时针顺序表示每一块披萨的大小。

输出格式

输出一行一个整数，代表小珅能获得的披萨大小总和的最大值。

输入输出样例

2
1 2 3 4 5 6

10

2
8 9 8 6 1 1

16

说明/提示

说明/提示

样例1解释

第一轮小珅选取大小为4的披萨，小泽取逆时针相邻的3，另一位伙伴取顺时针相邻的5； 第二轮小珅选取剩余的6，小泽取逆时针相邻的2，另一位伙伴取顺时针相邻的1； 小珅获得的总大小为$4+6=10$，是最优结果。

样例2解释

最优方案是两轮都选取大小为8的披萨；如果先手选择9，同伴会拿走相邻的8，最终小珅的总和达不到最大值。

数据范围

$1 \le n \le 100,\ 1 \le a_i \le 1000$

1
1 2 3

3