Did I miss the lethal?

How much damage can you deal with two "Soulfire"s in hand? 8? Are you sure?


-skyline- is playing Hearthstone, and his favorite class is Warlock. There's a special mechanism designed for cards of the Warlock class that after playing some cards from hand, one may need to discard some cards from the remaining hand randomly.



-skyline- has a hand of $n$ cards, with each card can deal some damage, but also possibly would discard some other cards from hand after playing. He is planning for a lethal turn. As a professional player of Hearthstone, he doesn't believe in his luck, so he wants to calculate that in the worst case, what is the maximum damage he can deal using this hand(We ignore the mana costs of the cards and assume that every card can be played, if not discarded).

Formally, there are $n$ cards in -skyline-'s hand, and the $i$th card has two properties $d_i$ and $a_i$, denoting the damage it can deal and the number of cards one needs to discard after playing this card, respectively.

-skyline- can choose the order to play cards from his hand, one by one. After he chooses to play the $i$th card from his hand(after playing, this card no longer exists in his hand), he would deal $d_i$ damage to the enemy hero, then $a_i$ cards from his remaining hand are uniformly chosen at random, then discarded(If currently -skyline- has a hand of less than $a_i$ cards, then all cards in his hand would be discarded). After a card is discarded from hand, it can not be played anymore.

-skyline- wants to choose the best strategy, such that in the worst case, he would deal the maximum number of total damage to the enemy hero. Please help -skyline- find out what this total damage is.

The first line contains a number $T(1\leq T\leq 20)$, denoting the number of test cases.

The first line of each test case contains one number $n(1\leq n\leq 200)$, denoting the number of cards in -skyline-'s hand.

Then $n$ lines follow. The $i$th line contains two integers $d_i(1\leq d_i\leq 10^7)$ and $a_i(1\leq a_i\leq 4)$, denoting the damage the $i$th card can deal and the number of cards one needs to discard after playing the $i$th card, respectively.

It is guaranteed that $\sum n \leq 2000$ over all test cases.

For each test case, output an integer in one line, denoting the maximum number of total damage -skyline- can deal to the enemy hero in the worst case.

2
3
3 1
4 2
5 2
6
10 1
10 1
15 2
20 3
20 3
25 4

7
40

For the first test case of the sample, the optimal strategy for -skyline- is to play the first card, then play the only remaining card that is not discarded.
In this case, -skyline- can deal a total of 3+4=7 damage to the enemy hero in the worst case.

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）