Powering the Hero (easy version)

题意翻译

有一副由 $n$ 张卡组成的牌，每一张牌有一个力量值，卡牌分为两种类型： + 对于一张英雄卡，它的力量值总是 $0$。 + 对于一张附加卡，其力量值总为 **正数**。 你可以对这副牌做以下操作： + 从牌堆顶端取走一张牌； + 如果这张牌是附加牌，你可以把它放到你的附加牌堆的 **堆顶**，或者直接丢弃； + 如果这张牌是英雄牌，那么附加牌堆顶的牌的力量值会赋给当前英雄卡（如果附加牌堆非空），之后其会加入你的军队，并且消耗所用附加牌。 你的任务是用这些操作集结一支 **最大总力量值的** 军队。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

6
6
8
9
4

说明

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 $ .

题目大意：
这是一道简单版本的问题，与难题的区别仅在于对n和t的限制。

有一副由n张卡组成的牌，每张卡都有一个力量值。卡牌分为两种类型：
- 英雄卡，其力量值总是0；
- 附加卡，其力量值总是正数。

你可以对这副牌执行以下操作：
- 从牌堆顶端取走一张牌；
- 如果这张牌是附加牌，你可以将其放到你的附加牌堆的堆顶，或者直接丢弃；
- 如果这张牌是英雄牌，那么附加牌堆顶的牌的力量值会赋给当前英雄卡（如果附加牌堆非空），之后英雄卡会加入你的军队，并消耗掉所用的附加牌。

你的任务是使用这些操作来集结一支最大总力量值的军队。

输入输出格式：
输入格式：
第一行输入数据包含一个整数t（1≤t≤1000）——测试用例的数量。

每个测试用例的第一行包含一个整数n（1≤n≤5000）——牌堆中的卡牌数量。

每个测试用例的第二行包含n个整数\(s_1, s_2, \dots, s_n\)（\(0 \le s_i \le 10^9\)）——从顶到底的卡牌力量值。

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

输出格式：
输出t个数字，每个数字是对应测试用例的答案——可以实现的军队最大可能总力量值。

输入输出样例：
输入样例 #1：
```
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
```
输出样例 #1：
```
6
6
8
9
4
```
说明：
在第一个样例中，你可以取附加卡1和2。两张英雄卡将获得3点力量。如果你取走所有附加卡，其中一张将不会被使用。

在第二个样例中，牌堆顶部的英雄卡无法被增强，其余的可以用2和3点力量的附加卡增强，并获得6点总力量。

在第四个样例中，你可以取附加卡1、2、3、5，并跳过附加卡6，然后英雄卡4将用附加卡3的力量5点增强，英雄卡7将用附加卡5的力量4点增强。4+5=9。题目大意： 这是一道简单版本的问题，与难题的区别仅在于对n和t的限制。 有一副由n张卡组成的牌，每张卡都有一个力量值。卡牌分为两种类型： - 英雄卡，其力量值总是0； - 附加卡，其力量值总是正数。 你可以对这副牌执行以下操作： - 从牌堆顶端取走一张牌； - 如果这张牌是附加牌，你可以将其放到你的附加牌堆的堆顶，或者直接丢弃； - 如果这张牌是英雄牌，那么附加牌堆顶的牌的力量值会赋给当前英雄卡（如果附加牌堆非空），之后英雄卡会加入你的军队，并消耗掉所用的附加牌。 你的任务是使用这些操作来集结一支最大总力量值的军队。 输入输出格式： 输入格式： 第一行输入数据包含一个整数t（1≤t≤1000）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤5000）——牌堆中的卡牌数量。 每个测试用例的第二行包含n个整数\(s_1, s_2, \dots, s_n\)（\(0 \le s_i \le 10^9\)）——从顶到底的卡牌力量值。 保证所有测试用例的n之和不超过5000。 输出格式： 输出t个数字，每个数字是对应测试用例的答案——可以实现的军队最大可能总力量值。 输入输出样例： 输入样例 #1： ``` 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 ``` 输出样例 #1： ``` 6 6 8 9 4 ``` 说明： 在第一个样例中，你可以取附加卡1和2。两张英雄卡将获得3点力量。如果你取走所有附加卡，其中一张将不会被使用。 在第二个样例中，牌堆顶部的英雄卡无法被增强，其余的可以用2和3点力量的附加卡增强，并获得6点总力量。 在第四个样例中，你可以取附加卡1、2、3、5，并跳过附加卡6，然后英雄卡4将用附加卡3的力量5点增强，英雄卡7将用附加卡5的力量4点增强。4+5=9。