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

题目描述

$\red{TeaLand }$正在举办第一届 $\red{TeaCuP}$！他们准备设置一个金牌（第一名），两个银牌（第 二、三名）和四个铜牌（第四到七名）。

赞助商们为获奖者准备了 $\red{N }$件奖品，第 $\red{i }$件奖品的价值为 $\red{A_i，}$每个获奖者会获得一 个奖品，设第 $\red{i }$名获得的奖品价值为 $\red{P_i,}$选手想要 $\red{P_i }$满足以下条件：

$\red{1. P_1 ≥}$ $\red{P_2 ≥}$ $\red{P_3 ≥}$ $\red{P_4 ≥}$ $\red{P_5 ≥}$ $\red{P_6 ≥}$ $\red{P_7.}$

$\red{2. P_1 < P_2 + P_3 < P_4 + P_5 + P_6 + P_7.}$

给定奖品的价值 $\red{A_i，}$你需要最大化 $\red{P_i }$之和，如果不存在任意一种方案则输出 $\red{-1}$。

输入格式

第一行一个整数 $\red{N }$表示奖品个数。

第二行 $\red{N }$个整数 $\red{A_i }$表示奖品的价值。

输出格式

如果不存在方案则输出 $\red{-1，}$否则输出最大的 $\red{P_i }$之和。

样例

输入样例1

7
1 2 3 4 5 6 7

输出样例1

-1

输入样例2

8
1 2 3 4 5 6 7 8

输出样例2

35

输入样例3

10
5 5 5 5 5 5 10 5 5 5

输出样例3

35

提示

对于 $\red{20\% }$的数据保证 $\red{N ≤}$ $\red{10}$。

对于 $\red{50\% }$的数据保证 $\red{N ≤}$ $\red{10^3}$。

对于所有测试点保证 $\red{7 ≤}$ $\red{N ≤}$ $\red{5 \times 10^5}$ , $\red{1 ≤}$ $\red{A_i ≤}$ $\red{2 \times 10^8}$。