Codeforces Round 855 (Div. 3) |
---|
Finished |
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:
You can do the following with the deck:
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.
553 3 3 0 060 3 3 0 0 371 2 3 0 4 5 071 2 5 0 4 3 053 1 0 0 4
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$$$.
Name |
---|