Junkyeom とその友人である Myung と Myeong は、1つの金メダル（1位）、2つの銀メダル（2位、3位）、および4つの銅メダル（4位、5位、6位、7位）を授与するプログラミングコンテストの開催を計画しています。

スポンサーからコンテストのために $N$ 枚のギフトカードが提供され、$i$ 番目のカードの価値は $A_i$ です。各メダリストにはちょうど1枚のカードが授与されます。$i$ 位の出場者に授与されるカードの価値を $P_i$ とします。以下の2つの不等式が成り立つ場合、その分配は「公平」であるとみなされます。

$$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$ の値が与えられたとき、公平な賞品の分配が存在するかどうかを判定してください。存在する場合は、公平な分配における $P_i$ の合計の最大値を出力してください。

入力

入力の1行目には、ギフトカードの枚数を表す整数 $N$ ($7 \leq N \leq 5 \cdot 10^5$) が含まれます。 2行目には、$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