该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

众所周知，TaopiTTT是个赛马娘玩家，11月23日即将在繁中服举办群英联赛，比赛指定场地为 新潟 草地 1000m 直线 夏 午，为了给他的爱马取得英雄传说称号，他开始培育本次参赛的战马。

题目描述

现在，TaopiTTT要培育战马了，我们定义战力值为他所培养的战马的战力值之和，当且仅当战力值大于匹配的其他玩家时，他能赢下群英联赛拿下称号。
为了简化描述，我们可以假设他在培育开始前拿到了一个包含$n$张卡的卡堆，其中：

• 马娘卡：这种卡战力值总为0
  
• 支援卡：这种卡的战力值总为正整数
  

培育开始后，TaopiTTT可以做以下操作：

• 从卡堆顶部取出一张牌；
• 如果这张牌是支援卡，他可以将其放在支援卡堆顶部，或者丢弃；
• 如果这张牌是马娘卡，则他可以将支援卡堆顶部的战力值加到该马娘的战力值上（如果支援卡堆不为空），之后该马娘加入他的出战队伍，并且使用过的支援卡被丢弃。
  

因为TaopiTTT在新卡池中大败而归，心情非常低落，所以他委托你帮助他培养战马，让他的出战队伍的总战力值最大。

输入格式

第一行输入数据包括一个整数$T$，表示测试中的总样例数

对于每一组输入数据第一行包括一个整数 $n$ ($1 \le n \le 5000$)，表示TaopiTTT拿到的卡牌数量

第二行包含$n$个整数$s_1, s_2, \dots, s_n$ ($0 \le s_i \le 10^9$) ，表示按自上而下顺序排序的卡牌战力值

保证所有测试数据中$n$总和不超过$5000$

输出格式

对于每个测试样例输出一行，包含一个数字$t$表示测试样例的答案，即TaopiTTT出战队伍能达到的最大战力

样例数据

5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4

6
6
8
9
4

样例解释

在第一个测试数据中，你可以为两位马娘分别获得3点战力，因此最后输出最大战力为6。

在第二个样例中，开始时位于卡堆顶部的马娘无法获得战力，其他马娘可以正常获得战力，因此最后最大战力为6

在第三个样例中，对于第一位马娘，可以通过丢弃战力值为1、2的支援卡，从而获取获得3点战力，对于第二位马娘，可以丢弃战力值为4的支援卡，从而获得5点战力，因此最后最大战力为8