构造故事
题号:NC277596
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,\,\mathcal S 今天在数学课上学习了三角形,他回家立马拿出了自己的 n 根火柴,想知道从这 n 根火柴中任选 3 根,能否组成一个周长最大的三角形。
\,\,\,\,\,\,\,\,\,\,由于小 \mathcal S 只会暴力枚举,所以他把这个问题交给了你,你能帮他解决这个问题吗?

输入描述:

\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\le T\le 20\right) 代表数据组数,每组测试数据描述如下:
\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n\left( 3\le n\le 10^4\right) 代表小 \mathcal S 的火柴数量。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( 1\le a_i \le 10^9\right) 代表每根火柴的长度。

输出描述:

\,\,\,\,\,\,\,\,\,\,对于每一组测试数据,在一行上输出一个整数,代表能组成周长最大三角形的周长;如果无论如何都无法组成三角形,直接输出 -1
示例1

输入

复制
3
6
2 2 10 4 10 6
5
6 1 5 3 3
5
2 2 4 10 6

输出

复制
26
14
-1

说明

\,\,\,\,\,\,\,\,\,\,对于第一组测试数据,有两个合法的三角形 (4,10,10)(6,10,10)