澄海3C

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

WAVwind有段时间非常迷恋澄海3C,为什么呢?因为它非常喜欢里面的剑圣和恶魔猎手(或者黑暗游侠和光明游侠)合体的熊猫,这样既有了能力更强的英雄,而减少了操作。WAVwind常常幻想,如果每个英雄都可以和任意的英雄(本来的或合成的)合体,那游戏肯定会更精彩。现在,我们假设这个幻想已经成真,但是每次合体都要花钱(比如剑圣价值A金币,恶魔猎手价值B金币,那么他们两合体需要花费A+B金币的钱)WAVwind很想知道最少花多少钱可以将所有英雄合体.。已知有N个英雄可选,每个英雄有个价值Ai,每次合体得到的新英雄的价值是合体的两个英雄的价值之和。问:为了完成N个英雄的全部合体,WAVwind最少需要花费多少钱?

Input

多组测试数据,一个整数T,表示测试数据个数。每组测试数据以一个整数N开始(1<=N<=100),表示可选英雄个数。下面接着有N个整数,表示每个英雄的价值。

Output

WAVwind最少花费的金币。

Sample Input

1
4
2  7   7   6

Sample Output

 44

Hint

Source

WAVwind@water

提交代码