Junkyeom 和他的朋友 Myung 以及 Myeong 计划举办一场编程竞赛，奖项包括一枚金牌（第 1 名）、两枚银牌（第 2、3 名）和四枚铜牌（第 4、5、6、7 名）。

赞助商为比赛提供了 $N$ 张礼品卡，其中第 $i$ 张卡的价值为 $A_i$。每位获奖者将获得且仅获得一张卡。设 $P_i$ 为颁发给第 $i$ 名选手的礼品卡的价值。如果满足以下两个不等式，则该分配被认为是公平的：

$$P_1 \geq P_2 \geq P_3 \geq P_4 \geq P_5 \geq P_6 \geq P_7$$

以及

$$P_1 < P_2 + P_3 < P_4 + P_5 + P_6 + P_7$$

给定 $A_i$ 的值，判断是否存在公平的奖品分配方案。如果存在，输出公平分配方案下 $\sum_{i=1}^7 P_i$ 的最大可能值。

输入格式

第一行包含一个整数 $N$，表示礼品卡的数量（$7 \leq N \leq 5 \cdot 10^5$）。

第二行包含 $N$ 个整数 $A_i$，表示礼品卡的价值（$1 \leq A_i \leq 2 \cdot 10^8$）。

输出格式

如果不存在公平的奖品分配方案，输出 $-1$。

否则，输出一个整数：公平分配方案下礼品卡总价值的最大可能值。

样例

样例输入 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