题目描述

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

有一副包含 $n$ 张牌的牌堆，每张牌都有其对应的力量值。牌分为两种类型：

• 英雄牌，这种牌的力量值总是等于 $0$；
• 奖励牌，这种牌的力量值总是正数。

你可以对牌堆进行如下操作：

• 从牌堆顶取出一张牌；
• 如果这张牌是奖励牌，你可以将其放在你的奖励牌堆顶，或者丢弃；
• 如果这张牌是英雄牌，则可以将你奖励牌堆顶的力量值加到该英雄的力量上（如果奖励牌堆不为空），之后该英雄加入你的军队，并且使用过的奖励牌被丢弃。

你的任务是通过这些操作，使你组建的军队的总力量最大。

输入格式

输入的第一行包含一个整数 $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$。

输出格式

输出 $t$ 行，每行一个整数，表示每个测试用例中可以获得的军队最大总力量。

说明/提示

在第一个样例中，你可以取奖励牌 $1$ 和 $2$。两个英雄牌都能获得 $3$ 的力量。如果你取了所有奖励牌，其中一个奖励牌将无法被使用。

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

在第四个样例中，你可以取奖励牌 $1$、$2$、$3$、$5$，跳过奖励牌 $6$，这样英雄 $4$ 能用奖励牌 $3$ 增强 $5$，英雄 $7$ 能用奖励牌 $5$ 增强 $4$，$4+5=9$。

由 ChatGPT 4.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

6
6
8
9
4