페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8187
서브태스크

Job Completion 1초 1024MB

문제

Bessie the cow has N (1≤N≤2⋅10^5) jobs for you to potentially complete. The i-th one, if you choose to complete it, must be started at or before time s_i and takes t_i time to complete (0≤s_i≤10^{18},1≤t_i≤10^{18}).

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.


입력

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 s_i and t_i. 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⋅10^5.


출력

For each test case, the maximum number of jobs you can complete, on a new line.


부분문제

번호 점수 조건
#110점

Within the same test case, all t_i are equal.

#220점

N≤2000 , s_i,t_i≤2000

#330점

N≤2000

#440점

No additional constraints.


예제1

입력
3
2
14
12
2
23
12
3
14
23
12
출력
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.


출처

USACO 2024 December Gold

역링크