#2085 최대 삼각형 찾기

68  1 s   128 MB  

Description

N개의 봉이 있다. 이 봉들 중에서3개를 선택하여 삼각형을 만들려고 한다. 이 때 만들어 질 수 있는 삼각형들 중에 둘레의 길이가 가장 긴 삼각형을 찾으려고 한다. 이 경우 찾아진 삼각형 둘레 길이의 최대값을 출력하는 프로그램을 작성하라.

Input

첫 줄에는 테스트 케이스 수 T(1 <= T <= 10)가 입력된다. 다음 줄부터 봉의 개수N(3<= N <= 10,000)이 입력되고 그 다음 줄에 봉의 길이(1 <= 봉의 길이<= 5,000) N개가T 만큼 반복해서 주어진다.

Output

각 테스트 케이스 별로 찾아진 삼각형 둘레 길이의 최대값을 한 줄에 하나씩 출력한다. 만약 주어진 봉들로 삼각형이 만들어질 수 없는 경우에는0을 출력한다.

Sample Input

Sample Output

2
5
2 10 3 5 4
4
4 5 10 20
12
0

Source

동의대학교 멀티미디공학과 우영운(2013년 4월 23일)