Bạn đang đứng trên một gờ đá trong rừng nhiệt đới, và tình yêu duy nhất của đời bạn đang đứng trên một gờ đá tương tự ở phía bên kia của một đầm lầy đầy rắn, cá sấu và nhiều sinh vật khó chịu khác. May mắn thay, có một số dây leo treo từ vòm lá của rừng trên đầm lầy, và thậm chí may mắn hơn, bằng cách nào đó bạn đã nắm được sợi dây đầu tiên trong số này (xem các hình minh họa bên dưới). Vòm lá của rừng ở độ cao không đổi, và cả hai gờ đá đều ở cùng độ cao với vòm lá. Các dây leo chỉ đơn giản là những đoạn dây treo từ vòm lá tại các điểm nhất định, với độ dài khác nhau.

Nếu bạn là một anh hùng hư cấu, bạn sẽ chỉ việc đu dây một cách cuồng nhiệt và hò hét, tại một thời điểm nào đó buông sợi dây đang giữ, bay trong không trung một lúc, bắt lấy một sợi dây khác, đu tiếp, và sau vài lần lặp lại, bạn sẽ ôm được tình yêu duy nhất của mình trong tay. Tiếc thay, bạn không phải là anh hùng hư cấu, và nếu bạn thử làm vậy, có lẽ hò hét sẽ là phần duy nhất bạn thực hiện tốt.

Kế hoạch của bạn thận trọng hơn một chút. Bạn sẽ đu trên sợi dây đang giữ, nhưng thay vì buông tay, bạn sẽ bắt lấy một sợi dây khác. Sau đó, bạn sẽ từ từ và cẩn thận leo lên sợi dây ban đầu của mình, sao cho sợi dây mới bạn đang giữ sẽ trở nên nằm ngang - hoặc đạt đến toàn bộ chiều dài của nó, hoặc đạt đến khoảng cách giữa hai sợi dây, tùy theo giá trị nào nhỏ hơn. Sau đó, bạn sẽ nghỉ ngơi một chút và đu tiếp để lặp lại quá trình này. Lưu ý rằng bạn không nhất thiết phải bắt sợi dây đầu tiên bạn gặp khi đang đu, bạn có thể thích đu xa hơn một chút và bắt một sợi dây ở xa hơn. Bạn cũng có thể leo lên sợi dây bạn đang đu qua lại để giảm khoảng cách giữa bạn và gốc của sợi dây. Thực tế, điều này có nghĩa là bạn có thể bắt bất kỳ sợi dây nào mà sợi dây của bạn cắt qua khi đang đu. Lưu ý rằng bạn sẽ không leo xuống dây khi đang đu.

Một điều khác biệt nữa giữa bạn và bất kỳ anh hùng hư cấu nào là trước khi bắt đầu toàn bộ quy trình khá rủi ro này, bạn muốn biết liệu thực sự có thể sang được bờ bên kia của khu rừng theo cách này hay không. Và đây là câu hỏi bạn phải trả lời trong bài toán này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test chứa số lượng dây leo \(N\). \(N\) dòng mô tả các dây leo tiếp theo, mỗi dòng gồm một cặp số nguyên \(d_i\) và \(l_i\) - tương ứng là khoảng cách của dây leo so với gờ đá của bạn và chiều dài của dây leo. Dòng cuối cùng của bộ test chứa khoảng cách \(D\) đến gờ đá nơi tình yêu của bạn đang đợi. Bạn bắt đầu bằng việc nắm giữ sợi dây đầu tiên.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là YES hoặc NO, cho biết liệu bạn có thể đến được với tình yêu của mình hay không, dựa trên các quy tắc trên.

Ràng buộc

• \(0 < d_i, l_i, D \le 10^9\).
• \(T \le 30\).
• \(d_i < d_{i+1}\).
• Vì bạn giữ sợi dây đầu tiên, \(d_0 \le l_0\).
• \(d_{N-1} < D\).

Phân nhóm

• Test set 1 (Visible Verdict): \(1 \le N \le 100\).
• Test set 2 (Hidden Verdict): \(1 \le N \le 10000\). Tổng số dây leo trong tất cả các bộ test không quá 60000.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
3
3 4
4 10
6 10
9
3
3 4
4 10
7 10
9
2
6 6
10 3
13
2
6 6
10 3
14

Case #1: YES
Case #2: NO
Case #3: YES
Case #4: NO

Nguồn

Google Code Jam 2012, Vòng 2, bài Swinging Wild.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.