Джанкём и его друзья Мён и Мён планируют провести соревнование по программированию, в котором будут разыграны одна золотая медаль (первое место), две серебряные (второе и третье места) и четыре бронзовые (четвертое, пятое, шестое и седьмое места).

Спонсоры предоставили $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$ определите, существует ли справедливое распределение призов. Если существует, выведите максимально возможную сумму $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