← 返回题目列表

Codeforces · 1251/E1

E1. 投票(简易版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是限制。

现在伯兰举行选举,您想赢得选举。更准确地说,你希望每个人都投票给你。

有 $$$n$$$ 个选民,有两种方法可以说服他们每个人投票给你。说服第 $$$i$$$ 选民的第一个方法是向他支付 $$$p_i$$$ 硬币。第二种方式是让$$$m_i$$$其他选民投票给你,第$$$i$$$个选民将免费投票。

此外,这种投票过程分几个步骤进行。例如,如果有五个选民,$$$m_1 = 1$$$、$$$m_2 = 2$$$、$$$m_3 = 2$$$、$$$m_4 = 4$$$、$$$m_5 = 5$$$,那么你可以购买第五个选民的选票,最终所有人都会投票给你。投票给您的一组人将发生如下变化:$$${5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}$$$。

计算你必须花费的最少硬币数量,以便每个人都投票给你。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 选民数量。

接下来的 $$$n$$$ 行包含选民的描述。第 $$$i$$$ 行包含两个整数 $$$m_i$$$ 和 $$$p_i$$$ ($$$1 \le p_i \le 10^9, 0 \le m_i < n$$$)。

保证所有测试用例的$$$n$$$ 总和不超过$$$5000$$$。

输出

对于每个测试用例,打印一个整数 - 您必须花费的最少硬币数量,以便每个人都投票给您。

示例

输入 #1

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

输出 #1

8
0
7

注意

在第一个测试用例中,您必须购买第三个投票者的投票。那么投票给你的人的集合将发生如下变化:$$${3} \rightarrow {1, 3} \rightarrow {1, 2, 3}$$$。

在第二个示例中,您不需要购买选票。投票给您的一组人将发生如下变化:$$${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}$$$。

在第三个测试用例中,您必须购买第二个和第五个选民的选票。那么投票给你的人的集合将发生如下变化:$$${2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$$$。