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

题目描述

伞伞训练营里有 $n$ 位小勇士，每位勇士都有一个“实力值”（数字越大越厉害）。现在他们要组队参加大学生比赛——每个队伍最多 $3$ 人（最少 $1$ 人），而且每位小勇士只能属于一个队伍。

伞伞想出了一个奇特的组队规则，每次都会这样做：

1. 从还没组队的人里，找出实力值最小的人（如果有多个最小的，随便选一个）；
2. 再从还没组队的人里，找出 实力值最大的两位小勇士（如果有多个最大的，随便选两个）；
3. 让这 1个最小 + 2个最大 组成一队！

一直重复，直到剩下的人不够三人。如果最后剩了 $1$ 个或 $2$ 位小勇士，那他们就自动组成最后一队（哪怕人数不够 $3$ 个）。

很显然，最后队伍的总数是 $⌈\frac{n}{3}⌉$（也就是 $n$ 除以 $3$ 再向上取整）。

一个队伍的实力 = 队里所有人实力值加起来。

现在，伞伞在正式组队之前，可以使用至多一次 “实力变形魔法”：他可以把任意一位小勇士的实力值，瞬间变成当前所有勇士中实力值最大的那个值（也就是变成全场最高！）。这样队伍的实力就会发生变化。

伞伞想知道：使用魔法之后再进行组队，最终组成的所有队伍中实力值总和最大的那个队伍，最多能有多强？

输入格式

从文件 morph.in 读入数据。 第一行包含一个正整数 $n$​​，含义如上所述。

第二行包含 $n$ 个正整数 $a_i$，表示小勇士们的实力值。

输出格式

输出到文件 morph.out。 一个整数，表示使用魔法后，实力最强的队伍的实力总和的最大可能值。

5
1 2 3 4 5

12

9
100 2 10 10 99 99 100 1 100

210

解释

在第一组数据中，若使第一位小勇士的实力值变成 $5$，组队的情况为$(2,5,5)$，$(3,4)$，队伍实力值最高为 $12$；

若使第二位小勇士的实力值变成 $5$，组队的情况为$(1,5,5)$，$(3,4)$，队伍实力值最高为 $11$；

若使第三位小勇士的实力值变成 $5$，组队的情况为$(1,5,5)$​，$(2,4)$，队伍实力值最高为 $11$；

若使第四位小勇士的实力值变成 $5$，组队的情况为$(1,5,5)$，$(2,3)$，队伍实力值最高为 $11$；

若使第五位小勇士的实力值变成 $5$，组队的情况为$(1,4,5)$，$(2,3)$，队伍实力值最高为 $10$；

因此，实力最强的队伍的实力值最高为 $12$。

样例 3

见 morph3.in 与 morph3.ans。

样例 4

见 morph4.in 与 morph4.ans。

样例 5

见 morph5.in 与 morph5.ans。

数据规模与约定

下发文件分别对应子任务 $1,2,3$。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 3 \times 10^5,0 \leq a_i \leq 10^9$。

时空限制：$1$ 秒 / $256\,\mathrm{MiB}$。