Junkyeom và những người bạn của mình là Myung và Myeong đang lên kế hoạch tổ chức một cuộc thi lập trình với một huy chương vàng (hạng 1), hai huy chương bạc (hạng 2 và 3), và bốn huy chương đồng (hạng 4, 5, 6, 7).

Các nhà tài trợ đã trao $N$ thẻ quà tặng cho cuộc thi, thẻ thứ $i$ có giá trị là $A_i$. Mỗi người đạt giải sẽ được trao đúng một thẻ. Gọi $P_i$ là giá trị của thẻ được trao cho thí sinh đạt hạng $i$. Việc phân phối được coi là công bằng nếu hai bất đẳng thức sau được thỏa mãn:

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

và

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

Cho các giá trị $A_i$, hãy xác định xem có tồn tại cách phân phối giải thưởng công bằng hay không. Nếu có, hãy in ra tổng giá trị lớn nhất có thể của $P_i$ cho một cách phân phối công bằng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$, số lượng thẻ quà tặng ($7 \leq N \leq 5 \cdot 10^5$).

Dòng thứ hai chứa $N$ số nguyên $A_i$: giá trị của các thẻ ($1 \leq A_i \leq 2 \cdot 10^8$).

Dữ liệu ra

Nếu không thể phân phối giải thưởng công bằng, in ra $-1$.

Nếu có thể, in ra một số nguyên duy nhất: tổng giá trị lớn nhất có thể của các thẻ quà tặng được phân phối công bằng.

Ví dụ

Dữ liệu vào 1

7
1 2 3 4 5 6 7

Dữ liệu ra 1

-1

Dữ liệu vào 2

8
1 2 3 4 5 6 7 8

Dữ liệu ra 2

35

Dữ liệu vào 3

10
5 5 5 5 5 5 10 5 5 5

Dữ liệu ra 3

35