Junkyeom wraz ze swoimi przyjaciółmi, Myungiem i Myeongiem, planuje zorganizować konkurs programistyczny, w którym przewidziano jeden złoty medal (pierwsze miejsce), dwa srebrne medale (miejsca 2 i 3) oraz cztery brązowe medale (miejsca 4, 5, 6 i 7).

Sponsorzy przekazali na konkurs $N$ kart podarunkowych, z których $i$-ta ma wartość $A_i$. Każdy medalista otrzyma dokładnie jedną kartę. Niech $P_i$ oznacza wartość karty przyznanej zawodnikowi, który zajął $i$-te miejsce. Rozdanie nagród uznaje się za sprawiedliwe, jeśli spełnione są następujące dwie nierówności:

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

oraz

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

Mając dane wartości $A_i$, sprawdź, czy istnieje sprawiedliwy podział nagród. Jeśli tak, wypisz maksymalną możliwą sumę $P_i$ dla sprawiedliwego podziału.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $N$, liczbę kart podarunkowych ($7 \leq N \leq 5 \cdot 10^5$). Druga linia zawiera $N$ liczb całkowitych $A_i$: wartości kart ($1 \leq A_i \leq 2 \cdot 10^8$).

Wyjście

Jeśli sprawiedliwy podział nagród jest niemożliwy, wypisz $-1$. W przeciwnym razie wypisz jedną liczbę całkowitą: maksymalną możliwą sumę wartości kart w sprawiedliwym podziale.

Przykład

Wejście 1

7
1 2 3 4 5 6 7

Wyjście 1

-1

Wejście 2

8
1 2 3 4 5 6 7 8

Wyjście 2

35

Wejście 3

10
5 5 5 5 5 5 10 5 5 5

Wyjście 3

35