거침없는 그네타기

당신은 정글의 한 절벽에 서 있고, 당신의 단 하나뿐인 진정한 사랑은 뱀과 악어를 비롯한 온갖 불쾌한 생물들이 우글거리는 늪 건너편의 비슷한 절벽에 서 있다. 다행히 늪 위 정글의 수관에는 여러 덩굴이 늘어져 있고, 더욱 다행히도 당신은 어떻게든 그 덩굴들 중 첫 번째 덩굴을 붙잡는 데 성공했다(아래 그림 참조). 정글의 수관은 일정한 높이에 있으며, 두 절벽 모두 수관과 같은 높이에 있다. 덩굴은 수관의 특정 지점에서 늘어진 단순한 선이며, 길이는 서로 다르다.

당신이 우연히 가상의 영웅이었다면, 그저 거칠게 그네를 타며 소리를 지르다가 어느 순간 붙잡고 있던 덩굴을 놓고, 잠시 공중을 날아 다른 덩굴을 붙잡아 다시 그네를 타는 일을 몇 번 반복한 뒤, 단 하나뿐인 진정한 사랑을 품에 안았을 것이다. 안타깝게도 당신은 가상의 영웅이 아니며, 그렇게 하려고 했다면 아마 소리 지르는 것만 잘 해냈을 것이다.

당신의 계획은 조금 더 신중하다. 붙잡고 있는 덩굴을 타고 그네를 타되, 놓는 대신 다른 덩굴을 붙잡는다. 그런 다음 새로 붙잡은 덩굴이 수평이 되도록 원래 덩굴을 천천히 조심스럽게 올라간다. 이때 새 덩굴은 전체 길이만큼 또는 두 덩굴 사이의 거리만큼 뻗으며, 둘 중 더 작은 쪽을 따른다. 그다음 잠시 쉬었다가 다시 그네를 타며 이 과정을 반복한다. 그네를 타다가 처음 마주치는 덩굴을 반드시 붙잡을 필요는 없다는 점에 유의하라. 조금 더 멀리 그네를 타서 더 멀리 있는 덩굴을 붙잡는 편을 택할 수도 있다. 현재 앞뒤로 그네를 타고 있는 덩굴을 올라가서 자신과 덩굴의 뿌리 사이의 거리를 줄일 수도 있다. 결과적으로 이는 그네를 타는 동안 자신의 덩굴이 가로지르는 어떤 덩굴이든 붙잡을 수 있음을 뜻한다. 그네를 타는 동안 덩굴을 내려가지는 않는다는 점에 유의하라.

당신을 어떤 가상의 영웅과도 구별해 주는 또 하나의 점은, 이 상당히 위험한 절차 전체를 시작하기 전에 이 방법으로 실제로 정글 반대편에 도달할 수 있는지 알고 싶다는 것이다. 이것이 이 문제에서 답해야 할 질문이다.

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 40초. 0 < $d_{i}$, $l_{i}$, D ≤ $10^{9}$. T ≤ 30. $d_{i}$ < $d_{i+1}$. 첫 번째 덩굴을 붙잡고 있으므로, $d_{0}$ ≤ $l_{0}$. $d_{N-1}$ < D.

테스트 세트 1 (Visible Verdict)

1 ≤ N ≤ 100.

테스트 세트 2 (Hidden Verdict)

1 ≤ N ≤ 10000. 모든 테스트 케이스에 있는 덩굴의 수를 합하면 최대 60000개이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 덩굴의 수 N이 주어진다. 이어지는 N개의 줄에는 덩굴이 설명되며, 각 줄에는 정수 쌍 $d_{i}$와 $l_{i}$가 주어진다. 이들은 각각 당신이 있는 절벽에서 덩굴까지의 거리와 덩굴의 길이이다. 테스트 케이스의 마지막 줄에는 단 하나뿐인 진정한 사랑이 있는 절벽까지의 거리 D가 주어진다. 처음에는 첫 번째 덩굴을 손으로 붙잡고 있다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 YES 또는 NO이다. 이는 위의 규칙에 따라 단 하나뿐인 진정한 사랑에게 도달할 수 있는지를 나타낸다.

첫 번째 케이스에서는 첫 번째 덩굴이 매달린 지점에서 3단위 떨어진 곳을 붙잡고 있다. 거칠게 그네를 타서 두 번째 덩굴을 지나치고, 세 번째 덩굴을 간신히 붙잡는다. 아래 그림은 시작 상황을 나타내며, 빨간 구간 안의 어느 곳에든 뿌리를 둔 덩굴에 도달할 수 있다:

휴식을 취한 뒤 세 번째 덩굴을 내려가고 첫 번째 덩굴을 올라가면, 시작점에서 세 단위 떨어진 곳에서 수관에 닿은 채 첫 번째와 세 번째 덩굴을 붙잡게 된다. 이제 첫 번째 덩굴을 놓고 다시 그네를 타서, 단 하나뿐인 진정한 사랑이 기다리는 절벽에 다시 한번 간신히 도달한다. 아래 그림은 세 번째 덩굴을 붙잡고 첫 번째 덩굴의 뿌리 쪽으로 올라간 뒤의 상황을 나타낸다. 마찬가지로 빨간 구간 안에 뿌리를 둔 어떤 덩굴에도 도달할 수 있다:

두 번째 케이스에서는 첫 번째 그네 타기로 세 번째 덩굴에 도달하지 못하므로, 유일한 선택은 두 번째 덩굴을 붙잡는 것이다. 하지만 그 덩굴은 시작점에서 네 단위 떨어진 곳에 매달려 있으므로, 첫 번째 덩굴을 올라가도 그네를 탈 수 있는 거리는 한 단위뿐이다. 이는 분명 세 번째 덩굴에 도달하기에는 너무 짧다. 따라서 늪 반대편은 고사하고 세 번째 덩굴에도 도달할 수 없다. 돌아갈 길을 찾는 편이 낫겠다(아니면 새로운 진정한 사랑을 찾거나).

세 번째 케이스에서는 붙잡고 있는 첫 번째 덩굴에서 그대로 그네를 타기만 하면 이동 경로가 두 번째 덩굴과 교차하지 않는다는 점에 유의하라. 두 번째 덩굴에 도달하려면 그네를 타는 동안 조금 올라가야 한다(다행히 그렇게 할 수 있다). 그네를 타는 동안에는 올라가기만 할 수 있고 내려갈 수는 없음을 기억하라(위로 향하는 덩굴은 팽팽해서 체중을 실을 수 있지만, 아래로 향하는 덩굴은 자유롭게 흔들리기 때문이다). 네 번째 케이스에서는 두 번째 덩굴에 도달할 수 있더라도 그 길이가 너무 짧아 마지막 절벽에 도달할 수 없다.