小苯的Polygon
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小苯面前有 n 根木棍,其中第 i 根木棍的长度为整数 a_i
\hspace{15pt}小苯现在想用这些木棍拼成一个封闭凸多边形,每根木棍都可以选择用或者不用,如果用的话只能用一次
\hspace{15pt}小苯想知道他可以组成的周长最小的封闭凸多边形的周长是多少。请你帮他算一算吧。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 100\right) 代表数据组数,每组测试数据描述如下:
\hspace{15pt}第一行输入一个正整数 n\left(1 \leqq n \leqq 100\right) 代表木棍的数量。
\hspace{15pt}第二行 n 个正整数 a_i\left(1 \leqq a_i \leqq 100\right) 代表每一根木棍的长度。

输出描述:

\hspace{15pt}对于每一组测试数据,新起一行。如果无法组成封闭凸多边形,直接输出 -1;否则,输出最小的封闭凸多边形周长。
示例1

输入

复制
2
8
1 2 3 5 6 7 8 9
3
1 2 3

输出

复制
11
-1

说明

\hspace{15pt}对于第一组数据,选择长度为 1,2,3,5 的这四根木棍,组成下图所示的封闭凸多边形,其周长为 1+2+3+5=11

图片

\hspace{15pt}对于第二组数据,无法组成封闭凸多边形,因此输出 -1