CF1800C1 Powering the Hero (easy version)

这是该问题的简单版本。它与困难版本的区别仅在于 $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 翻译