Junkyeom y sus amigos Myung y Myeong planean organizar un concurso de programación con una medalla de oro (primer lugar), dos de plata (lugares 2 y 3) y cuatro de bronce (lugares 4, 5, 6 y 7).

Los patrocinadores entregaron $N$ tarjetas de regalo para el concurso, donde la $i$-ésima tarjeta tiene un costo de $A_i$. Cada medallista recibirá exactamente una tarjeta. Sea $P_i$ el premio de la tarjeta otorgada al concursante que ocupa el $i$-ésimo lugar. La distribución se considera justa si se cumplen las siguientes dos desigualdades:

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

y

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

Dados los valores $A_i$, determine si existe una distribución justa de premios. Si existe, imprima la suma máxima posible de $P_i$ para una distribución justa.

Entrada

La primera línea de la entrada contiene un entero $N$, el número de tarjetas de regalo ($7 \leq N \leq 5 \cdot 10^5$).

La segunda línea contiene $N$ enteros $A_i$: los premios de las tarjetas ($1 \leq A_i \leq 2 \cdot 10^8$).

Salida

Si una distribución justa de premios es imposible, imprima $-1$.

De lo contrario, imprima un entero: la suma total máxima posible de los premios de las tarjetas distribuidas de manera justa.

Ejemplos

Entrada 1

7
1 2 3 4 5 6 7

Salida 1

-1

Entrada 2

8
1 2 3 4 5 6 7 8

Salida 2

35

Entrada 3

10
5 5 5 5 5 5 10 5 5 5

Salida 3

35