Junkyeom et ses amis Myung et Myeong prévoient d'organiser un concours de programmation avec une médaille d'or (première place), deux médailles d'argent (places 2 et 3) et quatre médailles de bronze (places 4, 5, 6 et 7).

Les sponsors ont offert $N$ cartes-cadeaux pour le concours, dont la $i$-ème a une valeur de $A_i$. Chaque médaillé doit recevoir exactement une carte. Soit $P_i$ la valeur de la carte attribuée au candidat occupant la $i$-ème place. La distribution est considérée comme équitable si les deux inégalités suivantes sont respectées :

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

et

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

Étant donné les valeurs $A_i$, déterminez si une distribution équitable des prix existe. Si c'est le cas, affichez la somme maximale possible des $P_i$ pour une distribution équitable.

Entrée

La première ligne de l'entrée contient un entier $N$, le nombre de cartes-cadeaux ($7 \leq N \leq 5 \cdot 10^5$).

La deuxième ligne contient $N$ entiers $A_i$ : les valeurs des cartes ($1 \leq A_i \leq 2 \cdot 10^8$).

Sortie

Si une distribution équitable des prix est impossible, affichez $-1$.

Sinon, affichez un entier : la somme totale maximale possible des cartes-cadeaux distribuées équitablement.

Exemples

Entrée 1

7
1 2 3 4 5 6 7

Sortie 1

-1

Entrée 2

8
1 2 3 4 5 6 7 8

Sortie 2

35

Entrée 3

10
5 5 5 5 5 5 10 5 5 5

Sortie 3

35