408082: GYM102979 J Junkyeom's Contest
Description
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.
InputThe 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$$$).
OutputIf a fair distribution of prizes is impossible, print $$$-1$$$.
Otherwise print one integer: the maximum possible total prize of the fairly distributed gift cards.
ExamplesInput7 1 2 3 4 5 6 7Output
-1Input
8 1 2 3 4 5 6 7 8Output
35Input
10 5 5 5 5 5 5 10 5 5 5Output
35