机器作业
Time Limit: 1000 MSMemory Limit: 5000 KB

Description

有n个作业需要在一台机器上执行,一个时刻机器上只能执行一个作业,每个作业可在单位时间内完成,作业i有截止时间di,当作业i在截止时间被执行完,则可获得pi的收益。求最大收益。


Input

第一行输入T(T<=10)表示有T组数据。每组数据先输入一个正整数N(1<=N<=50000),表示共有N个作业,随后输入N组(di,pi),表示每个作业的截止时间和收益。

Output

输出T行正整数,第i行表示第i组数据下能获得的最大收益。

Sample Input

3
1
4 10
4
1 5
1 6
2 3
3 10
4
2 5
2 6
3 3
3 10

Sample Output

10
19
21

Submit Your Code                        Discuss



苏ICP备2022026913号-1