Triangle

시간 제한3초메모리 제한512 MB

요약

N개의 막대 중 여섯 개를 골라 막대마다 한 번씩만 사용해 두 개의 삼각형을 만들고, 고른 여섯 막대 길이의 합의 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 정렬, 그리디, 투 포인터, 배열
정답자: 아직 제출이 없습니다

문제

There are $N$ sticks. The length of the $i$ -th stick is $a\_i$ . You want to choose six sticks and construct two triangles. Each stick should be used as an edge of one of the triangles. Also, the triangles should be non-degenerate.

Compute the maximum possible total length of the six chosen sticks. If two triangles can not be constructed this way, assume the total length is 0.

입력

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ). The $i$ -th of the next $N$ lines contains an integer $a\_i$ ( $1 \le a\_i \le 10^{15}$ ).

출력

Print the answer.

예제1

예제 1
입력
```
6
1
1
1
1
1
1
```
예상 출력
```
6
```