Keenan got $N$ sticks for his birthday! As part of his birthday present, he tries to make two triangles out of them!

In order for three sticks with lengths $a$, $b$, and $c$ to form a triangle, it must be the case that $a+b>c$, $b+c>a$, and $c+a>b$.

Keenan wants to maximize the sum of the perimeters of the two triangles he makes. Help him compute this! Note that a stick cannot be used in both triangles.

Constraints

$1\le N\le {10}^5$

$1\le a_i\le {10}^{15}$

Input Specification

The first line contains one integer, $N$.

Each of the next $N$ lines contains one integer, $a_i$.

Output Specification

Output the maximum possible sum of the perimeters of the two triangles Keenan makes. If Keenan cannot make two triangles, output 0.

Sample Input

6
1
1
1
1
1
1

Sample Output

6