다각형

면접 대비

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

요약

여러 개의 선분 길이가 주어질 때, 일부를 골라 넓이가 양수인 볼록 다각형을 만들 수 있는지 판단하고(가장 긴 변이 나머지 변 길이의 합보다 작아야 함) 가능한 최대 둘레를 구하며, 불가능하면 0을 출력한다.

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

문제

길이가 각각 $\ell_1, \ell_2, \dots, \ell_n$ 인 선분 $n$ 개가 주어진다. 이 선분들을 원하는 순서로, 그리고 반드시 전부 사용할 필요는 없이 사용해 만들 수 있는 볼록 다각형의 둘레의 최댓값을 구하라. 다각형은 퇴화하지 않아야 한다. 즉, 넓이가 양수여야 한다.

입력

첫 줄에 테스트 케이스의 수 $z$ 가 주어진다 ( $1 \le z \le 100\,000$ ). 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

테스트 케이스의 첫 줄에는 선분의 수 $n$ 이 주어진다 ( $1 \le n \le 100\,000$ ). 둘째 줄에는 $n$ 개의 정수 $\ell_1, \ell_2, \dots, \ell_n$ 이 주어진다 ( $1 \le \ell_i \le 10^9$ ). 이는 선분의 길이이다.

모든 테스트 케이스에 대한 $n$ 값의 합은 $1\,000\,000$ 을 넘지 않는다.

출력

각 테스트 케이스마다 주어진 선분으로 만들 수 있는 볼록 다각형의 둘레의 최댓값을 정수 하나로 출력한다. 그러한 다각형을 만들 수 없으면 0을 출력한다.

예제1

예제 1

입력

4
6
1 2 3 4 5 6
3
9 5 14
4
5 15 4 6
2
10 11

예상 출력