烟花

题号：NC286402
时间限制：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}$ 每朵烟花的绚烂度定义为这朵烟花的周长。请问所有烟花的绚烂度之和最大是多少？

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  代表笔的数量。
第二行输入  个整数  代表每一支笔的长度。

输出描述:

对于每组测试数据，新起一行。输出一个整数，代表所有烟花的绚烂度之和的最大值（可以为  ）。

示例1

输入

复制

1
7
150 145 180 380 350 300 520

输出

复制

说明

对于第一组测试数据，前三支笔拼成一个三角形，后四支笔拼成一个四边形。