小图灵又想写诗了。 小图灵一共有 个词汇,每个词汇都有着一定的魅力值 组,每个词组至多有 个词汇。每一个有 。小图灵需要将这 个词汇分成 个词汇的词组都会让小图灵产生大小为该词组中的 的魅力值的乘积的心动值。现在小图灵想请你帮她最大化所有产生的心动值之和。 输入格式 每个测试点含有多组测试数据。 首先输入一个整数 ,代表测试数据组数。 对于每一组测试数据,首先输入一行一个整数 ,代表小图灵的词汇数量。 接着输入一行 个整数 ,表示每个单词的魅力值。 输出格式 输出 行,每行一个整数表示你的答案。 样例输入 1 2 2 3 3 1 2 -3 4 4 5 1 2 -3 -4 个词 个词汇样例输出 1 2 2 14 样例解释 对于第一组数据,将单词分为 两组,心动值之和为 对于第二组数据,将单词分为 ; 两组,心动值之和为 。 大样例 见大样例压缩文件中的 poetry.in 与 poetry.ans。