덩굴 타고 늪 건너기 (스몰)

문제

정글 늪 이쪽 절벽에 당신이 서 있고, 늪 건너편 절벽에 사랑하는 사람이 서 있다. 늪에는 뱀과 악어가 우글거려서 걸어서 건널 수는 없다. 다행히 늪 위 정글 천장에서 덩굴이 여러 개 늘어져 있고, 당신은 이미 첫 번째 덩굴을 붙잡고 있다.

정글 천장의 높이는 어디서나 같고, 양쪽 절벽도 천장과 높이가 같다. 덩굴 $i$ 는 당신이 선 절벽에서 거리가 $d_i$ 인 지점에 매달려 수직으로 내려오며, 길이는 $l_i$ 이다. 처음에 당신은 절벽에서 덩굴 $0$ 을 잡고 있으므로, 매달린 지점에서 $d_0$ 만큼 떨어진 곳을 쥔 상태이다.

영화 주인공처럼 덩굴을 놓고 공중을 날아가는 방법은 쓰지 않는다. 매달린 지점에서 거리가 $r$ 인 곳을 쥐고 앞뒤로 흔들면, 팽팽하게 당겨진 덩굴이 천장 아래로 반지름 $r$ 인 반원 영역을 훑는다. 흔드는 도중에 덩굴을 타고 올라가 $r$ 을 줄일 수 있지만, 내려갈 수는 없다. 덩굴 $j$ 가 매달린 지점이 지금 쥔 덩굴의 매달린 지점에서 거리 $r$ 이내에 있으면 덩굴 $j$ 를 붙잡을 수 있다. 덩굴 $j$ 를 붙잡으면 원래 덩굴을 타고 천천히 올라가 새 덩굴을 수평으로 만든다. 그래서 덩굴 $j$ 에서 새로 쥐는 지점까지의 거리는 $l_j$ 와 두 덩굴이 매달린 지점 사이의 거리 중 작은 값이 된다. 잠시 쉰 다음 같은 과정을 되풀이한다.

흔들다가 처음 마주치는 덩굴을 꼭 잡을 필요는 없다. 그냥 지나쳐서 더 먼 덩굴을 잡아도 된다. 거리 $d_i$ 에 매달린 덩굴을 거리 $r$ 인 지점에서 쥔 상태에서 $d_i + r \ge D$ 이면 건너편 절벽에 닿는다. $D$ 는 건너편 절벽까지의 거리이다.

이 방법으로 늪을 건널 수 있는지 판별하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 덩굴의 개수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 정수 $d_i$ 와 $l_i$ 가 주어지며, 각각 절벽에서 덩굴이 매달린 지점까지의 거리와 덩굴의 길이이다. 테스트 케이스의 마지막 줄에는 건너편 절벽까지의 거리 $D$ 가 주어진다. 처음에 잡고 있는 덩굴은 첫 번째 덩굴이다.

제약 조건은 다음과 같다.

$1 \le T \le 30$
$1 \le N \le 100$
$0 < d_i, l_i, D \le 10^9$
$d_i < d_{i+1}$
$d_0 \le l_0$
$d_{N-1} < D$

출력

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

힌트

첫 번째 예제 케이스에서는 첫 덩굴을 매달린 지점에서 3만큼 떨어진 곳에서 쥐고 있다. 크게 흔들어 두 번째 덩굴을 지나치고 세 번째 덩굴을 간신히 붙잡는다. 아래 그림은 출발 상황이며, 빨간 구간 안에 매달린 덩굴은 모두 잡을 수 있다.

쉬고 나서 세 번째 덩굴을 내려간 뒤 첫 덩굴을 타고 올라가면, 출발점에서 3만큼 떨어진 천장 높이에서 첫 덩굴과 세 번째 덩굴을 함께 쥔 상태가 된다. 이제 첫 덩굴을 놓고 다시 흔들면 사랑하는 사람이 기다리는 절벽에 간신히 닿는다. 아래 그림은 세 번째 덩굴을 잡고 첫 덩굴의 매달린 지점으로 옮겨 간 뒤의 상황이며, 역시 빨간 구간 안의 덩굴은 모두 잡을 수 있다.

두 번째 예제 케이스에서는 첫 번째 흔들기로 세 번째 덩굴에 닿지 못하므로 두 번째 덩굴을 잡는 수밖에 없다. 그런데 두 번째 덩굴은 출발점에서 4만큼 떨어진 곳에 매달려 있어서, 첫 덩굴을 타고 올라가 봐야 흔들 수 있는 폭이 1밖에 남지 않는다. 세 번째 덩굴에조차 닿지 못하니 늪 건너편은 말할 것도 없다.

세 번째 예제 케이스에서는 첫 덩굴을 끝까지 늘어뜨린 채 흔들면 손이 두 번째 덩굴의 끝보다 아래를 지나간다. 그래도 쥐고 있는 덩굴 자체는 두 번째 덩굴과 교차하고, 흔들면서 조금 올라가면 두 번째 덩굴을 잡을 수 있다. 올라가는 것만 되고 내려가는 것은 안 된다. 손 위쪽의 덩굴은 팽팽해서 몸무게를 실을 수 있지만, 손 아래쪽의 덩굴은 그냥 흔들릴 뿐이기 때문이다.

네 번째 예제 케이스에서는 두 번째 덩굴까지는 갈 수 있지만, 그 덩굴이 너무 짧아서 마지막 절벽에 닿지 못한다.