도미노

시간 제한1초메모리 제한128 MB

요약

도미노 하나를 왼쪽이나 오른쪽으로 넘어뜨렸을 때 쓰러지는 최대 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 이분 탐색, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

야레크는 크리스마스 선물로 서로 다른 높이의 도미노 여러 개를 받아, 한 줄로 모두 세워 놓았습니다.

위치 $X$ 에 놓인 높이 $H$ 짜리 도미노를 오른쪽으로 넘어뜨리면, 위치 $X+1, X+2, \dots, X+H$ 에 있는 모든 도미노가 오른쪽으로 넘어집니다. 마찬가지로 위치 $X$ 에 놓인 높이 $H$ 짜리 도미노를 왼쪽으로 넘어뜨리면, 위치 $X-1, X-2, \dots, X-H$ 에 있는 모든 도미노가 왼쪽으로 넘어집니다. 이렇게 넘어진 도미노는 같은 방향으로 그다음 도미노들을 계속 넘어뜨립니다(연쇄 반응).

각 도미노의 위치와 높이가 주어질 때, 도미노 하나를 어느 한 방향으로 넘어뜨려 쓰러지는 도미노의 최대 개수를 구하세요.

입력

첫째 줄에 테스트 케이스의 수 $Z$ ( $1 \le Z \le 10$ )가 주어집니다.

각 테스트 케이스의 첫째 줄에는 도미노의 개수 $N$ ( $1 \le N \le 10^5$ )이 주어집니다. 이어지는 $N$ 개의 줄에는 각 도미노의 위치 $X$ 와 높이 $H$ ( $1 \le X, H \le 10^9$ )가 두 정수로 주어집니다. 도미노의 위치는 오름차순으로 주어집니다.

출력

각 테스트 케이스마다, 도미노 하나를 넘어뜨렸을 때 쓰러질 수 있는 도미노의 최대 개수를 한 줄에 하나씩 출력하세요.

예제2

예제 1
입력
```
1
4
1 2
4 1
5 2
7 1
```
예상 출력
```
3
```
예제 2
입력
```
1
6
1 1
2 1
3 1
4 1
5 1
6 1
```
예상 출력
```
6
```