408082: GYM102979 J Junkyeom's Contest

Junkyeom and his friends Myung and Myeong are planning to hold a programming contest with one gold (first place), two silver (places 2 and 3), and four bronze medals (places 4, 5, 6, 7).

The sponsors gave $$$N$$$ gift cards for the contest, $$$i$$$-th of them costs $$$A_i$$$. Each medalist shall be awarded exactly one card. Let $$$P_i$$$ be the prize for the card awarded to the contestant taking $$$i$$$-th place. The distribution is considered fair if the following two inequalities are held:

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

and

$$$$$$ P_1 < P_2 + P_3 < P_4 + P_5 + P_6 + P_7\text{.} $$$$$$

Given the values $$$A_i$$$, find out if a fair distribution of prizes exists. If it does, print the maximum possible sum of $$$P_i$$$ for a fair distribution.

The first line of input contains one integer $$$N$$$, the number of gift cards ($$$7 \le N \le 5 \cdot 10^5$$$).

The second line contains $$$N$$$ integers $$$A_i$$$: the prizes for the cards ($$$1 \le A_i \le 2 \cdot 10^8$$$).

If a fair distribution of prizes is impossible, print $$$-1$$$.

Otherwise print one integer: the maximum possible total prize of the fairly distributed gift cards.

7
1 2 3 4 5 6 7

-1

8
1 2 3 4 5 6 7 8

35

10
5 5 5 5 5 5 10 5 5 5

35