CF1800C1.Powering the Hero (easy version)

This is an easy version of the problem. It differs from the hard one only by constraints on $n$ and $t$.

There is a deck of $n$ cards, each of which is characterized by its power. There are two types of cards:

• a hero card, the power of such a card is always equal to $0$;
• a bonus card, the power of such a card is always positive.

You can do the following with the deck:

• take a card from the top of the deck;
• if this card is a bonus card, you can put it on top of your bonus deck or discard;
• if this card is a hero card, then the power of the top card from your bonus deck is added to his power (if it is not empty), after that the hero is added to your army, and the used bonus discards.

Your task is to use such actions to gather an army with the maximum possible total power.

这是一个该问题的简单版本。它与困难版本的唯一区别在于对 $n$ 和 $t$ 的约束条件。

有一副包含 $n$ 张卡牌的卡组，每张卡牌均具有一个“力量值”。卡牌分为两类：

• 英雄卡：其力量值恒为 $0$；
• 增益卡：其力量值恒为正数。

你可以对卡组执行以下操作：

• 从卡组顶部取出一张卡牌；
• 若取出的是增益卡，则可将其置于你的增益卡组顶部，或直接弃掉；
• 若取出的是英雄卡，则（若你的增益卡组非空）将增益卡组顶部卡牌的力量值加到该英雄卡的力量值上；随后，将该英雄卡加入你的军队，且已使用的增益卡被弃掉。

你的任务是通过上述操作，组建一支总力量值尽可能大的军队。

The first line of input data contains single integer $t$ ($1 \le t \le 1000$) — the number of test cases in the test.

The first line of each test case contains one integer $n$ ($1 \le n \le 5000$) — the number of cards in the deck.

The second line of each test case contains $n$ integers $s_1, s_2, \dots, s_n$ ($0 \le s_i \le 10^9$) — card powers in top-down order.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$）—— 表示牌组中卡片的数量。

每个测试用例的第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$0 \le s_i \le 10^9$）—— 表示从上到下各张卡片的点数。

保证所有测试用例的 $n$ 值之和不超过 $5000$。

Output $t$ numbers, each of which is the answer to the corresponding test case — the maximum possible total power of the army that can be achieved.

输出 $t$ 个数字，每个数字对应一个测试用例的答案——即所能达到的军队总战力的最大值。

In the first sample, you can take bonuses $1$ and $2$. Both hero cards will receive $3$ power. If you take all the bonuses, one of them will remain unused.

In the second sample, the hero's card on top of the deck cannot be powered up, and the rest can be powered up with $2$ and $3$ bonuses and get $6$ total power.

In the fourth sample, you can take bonuses $1$, $2$, $3$, $5$ and skip the bonus $6$, then the hero $4$ will be enhanced with a bonus $3$ by $5$, and the hero $7$ with a bonus $5$ by $4$. $4+5=9$.

在第一个样例中，你可以选择奖励 $1$ 和 $2$。两张英雄卡都将获得 $3$ 点力量值。若你选择全部奖励，则其中有一个奖励将无法使用。

在第二个样例中，牌堆顶部的英雄卡无法被增强，其余英雄卡可分别用奖励 $2$ 和 $3$ 进行增强，总共获得 $6$ 点力量值。

在第四个样例中，你可以选择奖励 $1$、$2$、$3$、$5$，跳过奖励 $6$；此时英雄 $4$ 将通过奖励 $3$ 获得 $5$ 点增强，英雄 $7$ 将通过奖励 $5$ 获得 $4$ 点增强。$4+5=9$。