本题需要文件读写(firework.in&firework.out)

叠甲

请不要在烟花爆竹禁放区燃放烟花爆竹。

题目描述

李华喜欢在除夕夜放烟花。特别是今年，他的期末考考的很好，所以他特别开心。

在李华所在的多邻国，不同烟花有不同的燃放时间，第 $i$ 个烟花需要 $t_i$ 分钟才能燃放完毕。这里的烟花很奇怪，需要底座来燃放。一般大家都有多个底座来同时燃放烟花。但是李华所在的小区只有 $1$ 个烟花底座，而且众所周知，一个底座在同一时刻只能同时燃放一个烟花。李华从时刻 $0$ 开始放第一发烟花。

定义：对于每个烟花，它的完成时间是指从时刻 $0$ 到它燃放结束的总时长。例如，若烟花燃放顺序为 $[3, 1, 2]$，则它们的完成时间分别为 $3$、$3+1=4$、$3+1+2=6$。

因为大家都在等待李华放完烟花，而且李华比较有公德心，所以李华希望所有烟花的完成时间之和最小（这样整体“等待”更少，后面的人可以更快放上烟花）。所以请你帮他安排燃放顺序，使得这个总完成时间最小，并输出该最小值。

输入格式

本题有多组输入数据

第一行输入数据组数 $T$（$0<t≤5$）。

每组数据第一行为正整数 $n$（$0<n≤500$），表示李华一共有 $n$ 个烟花。

第二行为 $n$ 个正整数 $t_1, t_2, \dots, t_n$（$0<t_i≤1000$，用空格分隔），表示每个烟花的燃放时间。

输出格式

对每组数据，输出一个正整数，表示最小的总完成时间（即所有烟花完成时间之和的最小值）。每组数据输出占一行。