정겸과 그의 친구들인 명과 명은 금상 1명(1등), 은상 2명(2등, 3등), 동상 4명(4등, 5등, 6등, 7등)을 수여하는 프로그래밍 대회를 개최하려고 합니다.

후원자들은 대회에 사용할 $N$개의 기프트 카드를 제공했으며, $i$번째 카드의 가격은 $A_i$입니다. 각 수상자에게는 정확히 하나의 카드가 수여됩니다. $i$등을 차지한 참가자에게 수여된 카드의 가격을 $P_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