삼각형

면접 대비

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

요약

막대 N개의 길이가 주어질 때, 여섯 개를 골라 넓이가 0이 아닌 삼각형 두 개를 만들 때의 최대 길이 합을 구합니다. 만들 수 없으면 0을 출력합니다.

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

문제

막대가 $N$ 개 있고, $i$ 번째 막대의 길이는 $a_i$ 이다. 막대 6개를 골라 삼각형 2개를 만들려고 한다. 고른 막대는 모두 두 삼각형 중 하나의 변으로 사용해야 하며, 두 삼각형은 모두 퇴화하지 않아야 한다(넓이가 0이면 안 된다). 고른 막대 6개 길이의 합이 최대가 되는 값을 구하라. 이렇게 삼각형 2개를 만들 수 없으면 합은 0이다.

입력

첫째 줄에 정수 $N$ ( $1 \le N \le 10^5$ )이 주어진다. 다음 $N$ 개의 줄에는 각각 정수 $a_i$ ( $1 \le a_i \le 10^{15}$ )가 한 줄에 하나씩 주어진다.

출력

답을 출력한다.

예제1

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