Bessie the cow has N (1≤N≤2⋅105) jobs for you to potentially complete. The i-th one, if you choose to complete it, must be started at or before time si and takes ti time to complete (0≤si ≤1018,1≤ti ≤1018).
What is the maximum number of jobs you can complete? Time starts at 0
, and once you start a job you must work on it until it is complete, without starting any other jobs in the meantime.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T, the number of independent test cases (1≤T≤10). Each test case is formatted as follows.
The first line contains N.
Each of the next N lines contains two integers si and ti . Row i+1 has the details for the ith job.
It is guaranteed that the sum of N over all test cases does not exceed 3⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, the maximum number of jobs you can complete, on a new line.
SAMPLE INPUT:
3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2
SAMPLE OUTPUT:
1
2
2
For the first test case, you can only complete one of the jobs. After completing one job, it will then be time 2 or later, so it is too late to start the other job, which must be started at time 1 or earlier.
For the second test case, you can start the second job at time 0 and finish at time 2, then start the first job at time 2 and finish at time 5.
SCORING:
Inputs 2: Within the same test case, all ti are equal.
Inputs 3-4: N≤2000, si ,ti ≤2000
Inputs 5-8: N≤2000
Inputs 9-16: No additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
