Voting (Easy Version)

简单难度和困难难度的唯一差别是数据范围 有一群选民，你想获得他们全部的选票，而对于第$i$选民，有着一个跟风值$m_i$，如果有其它不低于$m_i$个选民已经投票给你，那么他就会跟风一起投票给你；还有着一个贿赂值$p_i$，如果你可以付出$p_i$个硬币，那么他就会把票投给你 这种投票是分阶段进行的，例如，现在有五个选民他们的跟风值分别是$m_1=1$, $m_2=2$, $m_3=2$, $m_4=4$, $m_5=5$，然后你可以贿赂第五个选民，然后所有选民就会都投票给你，投票给你的选民变化为：$5→1,5→1,2,3,5→1,2,3,4,5$ 现在请你计算出最少需要多少个硬币来让所有选民投票给你 ### 输入格式 第一行是一个正整数$t(1≤t≤5000)$，表示测试用例数量 对于每个测试用例，第一行是一个正整数$n(1≤n≤5000)$，表示选民的数量 然后有$n$行，每行两个整数，第$i$行的两个整数$m_i, q_i$表示第$i$个选民的跟风值和贿赂值 $(1≤p_i≤10^9,0≤m_i<n)$ 数据保证所有样例的$n$之和不超过$5000$ ### 输出格式 对于每个测试样例，输出一个整数，表示能使所有人投票给你所需要的最少硬币数量

The only difference between easy and hard versions is constraints. Now elections are held in Berland and you want to win them. More precisely, you want everyone to vote for you. There are $ n $ voters, and two ways to convince each of them to vote for you. The first way to convince the $ i $ -th voter is to pay him $ p_i $ coins. The second way is to make $ m_i $ other voters vote for you, and the $ i $ -th voter will vote for free. Moreover, the process of such voting takes place in several steps. For example, if there are five voters with $ m_1 = 1 $ , $ m_2 = 2 $ , $ m_3 = 2 $ , $ m_4 = 4 $ , $ m_5 = 5 $ , then you can buy the vote of the fifth voter, and eventually everyone will vote for you. Set of people voting for you will change as follows: $ {5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5} $ . Calculate the minimum number of coins you have to spend so that everyone votes for you.

The first line contains one integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of test cases. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 5000 $ ) — the number of voters. The next $ n $ lines contains the description of voters. $ i $ -th line contains two integers $ m_i $ and $ p_i $ ( $ 1 \le p_i \le 10^9, 0 \le m_i < n $ ). It is guaranteed that the sum of all $ n $ over all test cases does not exceed $ 5000 $ .

For each test case print one integer — the minimum number of coins you have to spend so that everyone votes for you.

3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5

8
0
7

In the first test case you have to buy vote of the third voter. Then the set of people voting for you will change as follows: $ {3} \rightarrow {1, 3} \rightarrow {1, 2, 3} $ . In the second example you don't need to buy votes. The set of people voting for you will change as follows: $ {1} \rightarrow {1, 3, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 5, 6, 7} \rightarrow {1, 2, 3, 4, 5, 6, 7} $ . In the third test case you have to buy votes of the second and the fifth voters. Then the set of people voting for you will change as follows: $ {2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6} $ .