Triangle

Interview

Time limit3sMemory limit512 MB

Summary

Given N stick lengths, pick six to form two non-degenerate triangles and print the maximum total length, or 0 if that is impossible.

Level: Medium4 of 10
Topics: Sorting, Greedy, Array
Solved: No attempts yet

Problem

There are $N$ sticks. The length of the $i$ -th stick is $a_i$ . Choose six sticks and build two triangles. Each chosen stick must be used as an edge of one of the triangles, and both triangles must be non-degenerate (have positive area). Compute the maximum possible total length of the six chosen sticks. If two triangles cannot be built this way, the answer is 0.

Input

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ). Each of the next $N$ lines contains an integer $a_i$ ( $1 \le a_i \le 10^{15}$ ).

Output

Print the answer.

Examples1

Example 1
Input
```
6
1
1
1
1
1
1
```
Expected output
```
6
```