덩굴 타고 늪 건너기

당신은 정글의 절벽 위에 서 있다. 뱀과 악어가 우글거리는 늪 건너편, 같은 높이의 절벽에는 사랑하는 사람이 서 있다. 늪 위로는 정글 지붕에서 덩굴 여러 개가 늘어져 있고, 당신은 그중 첫 번째 덩굴을 겨우 붙잡았다. 지붕의 높이는 어디서나 같고 양쪽 절벽도 지붕과 높이가 같다. 덩굴은 지붕의 한 점에서 수직으로 늘어진 선분이며 길이는 저마다 다르다.

영화 속 주인공이라면 소리를 지르며 덩굴을 놓고 공중을 날아 다른 덩굴을 잡는 일을 몇 번 반복해 건너편에 닿을 것이다. 당신은 주인공이 아니므로 더 조심스러운 방법을 쓴다. 잡고 있는 덩굴에 매달려 흔들리다가, 그 덩굴을 놓지 않은 채로 다른 덩굴을 잡는다. 그다음 원래 덩굴을 타고 천천히 올라가서 새로 잡은 덩굴이 뿌리에서 손까지 수평이 되게 만든다. 이때 수평이 되는 길이는 그 덩굴의 전체 길이와 두 덩굴 뿌리 사이의 거리 중 작은 쪽이다. 잠시 쉰 다음 다시 흔들리며 같은 과정을 반복한다.

흔들리다 처음 마주친 덩굴을 반드시 잡아야 하는 것은 아니다. 더 멀리 흔들려 그 너머의 덩굴을 잡아도 된다. 흔들리는 동안 잡고 있는 덩굴을 타고 올라가 뿌리와의 거리를 줄일 수도 있다. 그래서 흔들리는 궤적이 스치는 덩굴이라면 무엇이든 잡을 수 있다. 다만 흔들리는 동안 덩굴을 타고 내려갈 수는 없다. 손 위쪽 덩굴은 팽팽해서 체중을 실을 수 있지만 손 아래쪽 덩굴은 자유롭게 흔들리기 때문이다.

이 위험한 시도를 시작하기 전에, 이 방법으로 건너편에 닿을 수 있는지부터 알아야 한다.

당신이 선 절벽을 좌표 0으로 두자. $i$번 덩굴은 좌표 $d_i$에서 늘어져 있고 길이는 $l_i$이다. $i$번 덩굴을 지붕에서 $r$만큼 내려온 지점에서 잡고 흔들리면 $|x - d_i| \le r$인 좌표 $x$를 모두 지나므로, $|d_j - d_i| \le r$인 $j$번 덩굴을 잡을 수 있다. 그렇게 $j$번 덩굴을 잡으면 지붕에서 $\min(l_j, |d_j - d_i|)$만큼 내려온 지점을 잡은 상태가 된다. 출발할 때는 절벽에서 $1$번 덩굴을 잡고 있으므로 처음 잡은 지점은 지붕에서 $d_1$만큼 내려온 곳이다. $i$번 덩굴을 지붕에서 $r$만큼 내려온 지점에서 잡고 있을 때 $d_i + r \ge D$이면 건너편 절벽에 닿는다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 덩굴의 수 $N$이 주어진다. 이어지는 $N$개의 줄에는 두 정수 $d_i$와 $l_i$가 주어진다. $d_i$는 당신이 선 절벽에서 덩굴 뿌리까지의 거리이고, $l_i$는 덩굴의 길이다. 테스트 케이스의 마지막 줄에는 사랑하는 사람이 선 절벽까지의 거리 $D$가 주어진다. 출발할 때 $1$번 덩굴을 잡고 있다.

제한:

• $1 \le T \le 30$
• $1 \le N \le 10000$
• $0 < d_i, l_i, D \le 10^9$
• $d_i < d_{i+1}$
• $d_1 \le l_1$
• $d_N < D$
• 모든 테스트 케이스의 덩굴 수 합은 $60000$ 이하다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 사랑하는 사람에게 닿을 수 있으면 YES, 닿을 수 없으면 NO이다.

아래에서 설명하는 네 경우는 첫 번째 예제 테스트다.

첫 번째 경우, 첫 덩굴을 뿌리에서 3만큼 떨어진 지점에서 잡는다. 흔들리면서 두 번째 덩굴을 지나쳐 세 번째 덩굴을 아슬아슬하게 잡는다. 아래 그림은 출발 상황이고, 빨간 구간 안에 뿌리가 있는 덩굴은 모두 잡을 수 있다.

쉬고 나서 세 번째 덩굴을 타고 내려간 뒤 첫 번째 덩굴을 타고 올라가면, 출발점에서 3만큼 떨어진 곳에서 지붕에 닿은 채로 첫 번째와 세 번째 덩굴을 함께 잡고 있게 된다. 이제 첫 번째 덩굴을 놓고 다시 흔들리면 사랑하는 사람이 기다리는 절벽에 아슬아슬하게 닿는다. 아래 그림은 세 번째 덩굴을 잡고 첫 번째 덩굴의 뿌리로 옮겨간 뒤의 상황이며, 잡을 수 있는 구간을 다시 빨간색으로 표시했다.

두 번째 경우, 첫 흔들림으로는 세 번째 덩굴에 닿지 못하므로 두 번째 덩굴을 잡을 수밖에 없다. 그 뿌리는 출발점에서 4만큼 떨어져 있어서 첫 덩굴을 타고 올라가도 흔들 수 있는 길이가 1뿐이고, 세 번째 덩굴에 닿기에는 턱없이 짧다. 결국 세 번째 덩굴조차 잡지 못한다.

세 번째 경우, 첫 덩굴을 그대로 잡고 흔들면 궤적이 두 번째 덩굴을 스치지 않는다. 흔들리는 동안 조금 타고 올라가야 두 번째 덩굴에 닿는다. 흔들리는 동안에는 올라갈 수만 있고 내려갈 수는 없다. 손 위쪽 덩굴은 팽팽하지만 아래쪽 덩굴은 자유롭게 흔들리기 때문이다.

네 번째 경우, 두 번째 덩굴을 잡을 수는 있지만 그 덩굴이 짧아 마지막 절벽에는 닿지 못한다.