Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
147 - The 17th Zhejiang University Programming Contest Sponsored by TuSimple - I
Course Selection System

Time Limit: 1 Second      Memory Limit: 65536 KB

There are n courses in the course selection system of Marjar University. The i-th course is described by two values: happiness Hi and credit Ci. If a student selects m courses x1, x2, ..., xm, then his comfort level of the semester can be defined as follows:

Edward, a student in Marjar University, wants to select some courses (also he can select no courses, then his comfort level is 0) to maximize his comfort level. Can you help him?

#### Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains a integer n (1 ≤ n ≤ 500) -- the number of cources.

Each of the next n lines contains two integers Hi and Ci (1 ≤ Hi ≤ 10000, 1 ≤ Ci ≤ 100).

It is guaranteed that the sum of all n does not exceed 5000.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

#### Output

For each case, you should output one integer denoting the maximum comfort.

#### Sample Input

2
3
10 1
5 1
2 10
2
1 10
2 10


#### Sample Output

191
0


#### Hint

For the first case, Edward should select the first and second courses.

For the second case, Edward should select no courses.

Submit    Status