Description

你正站在丛林中的一个岩架上，你的真爱正站在沼泽对岸的另一个相似的岩架上。沼泽中满是蛇、鳄鱼和各种令人不快的生物。幸运的是，丛林树冠上方悬挂着许多藤蔓，更幸运的是，你设法抓住了这些藤蔓中的第一根（见下图）。树冠高度恒定，两个岩架的高度也与树冠一致。藤蔓仅仅是从树冠某些点垂下来的线段，长度各不相同。

如果你是小说中的英雄，你会疯狂地荡着藤蔓大喊大叫，在某个时刻松手飞跃空中，抓住另一根藤蔓，再次荡起，如此反复，最终你会把你的真爱拥入怀中。不幸的是，你并不是小说英雄，如果你尝试这么做，可能唯一能做好的只有大喊大叫。

你的计划要谨慎得多。你会先在手中的藤蔓上荡起来，但不是松手，而是去抓住另一根藤蔓。然后你会慢慢小心地爬上原来的藤蔓，使你手中抓住的新藤蔓变成水平状态——要么拉到它的全部长度，要么拉到两根藤蔓之间的距离，以较小者为准。然后你会休息片刻，再次荡起来，如此反复。注意，你并不一定要抓住荡到的第一根藤蔓，你可以选择荡得更远，抓住更远的藤蔓。同样，你可以在荡动时爬上当前的藤蔓，以缩短你与藤蔓根部的距离。实际上，这意味着你可以抓住任何在你荡动时经过的藤蔓。注意，荡动时你不会向下爬藤蔓。

还有一点你与小说英雄不同，那就是在开始这场相当冒险的行动前，你想知道按照上述规则，你是否真的有可能到达对岸。这正是本题要你回答的问题。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为藤蔓数量 $N$。接下来 $N$ 行，每行两个整数 $d_i$ 和 $l_i$，分别表示第 $i$ 根藤蔓距离你所在岩架的距离，以及该藤蔓的长度。每组测试数据最后一行为你到真爱所在岩架的距离 $D$。你一开始手里抓着第一根藤蔓。

Output Format

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 为 "YES" 或 "NO"，表示你是否有可能按照上述规则到达你的真爱身边。

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

Hint

样例说明

在第一个样例中，你手中的第一根藤蔓距离其挂点有 3 个单位长度。你可以大幅荡动，越过第二根藤蔓，刚好抓住第三根。下图展示了初始状态，你能够到达任何根部在红色区间内的藤蔓：

休息后，你顺着第三根往下爬，顺着第一根往上爬，发现自己距离起点 3 个单位长度，正好碰到树冠并抓住第一和第三根藤蔓。现在你松开第一根，再次荡动，又刚好到达终点岩架，你的真爱在那等你。下图展示了你抓住第三根并爬到第一根根部后的状态。你同样可以到达任何红色区间内的藤蔓：

在第二个样例中，你第一次荡动无法到达第三根藤蔓，所以只能抓住第二根。然而，第二根距起点 4 个单位长度，即使你顺着第一根往上爬，也只能荡 1 个单位长度——显然不足以到达第三根藤蔓。因此你连第三根都到不了，更别说对岸了。你还是去找别的路（或新的真爱）吧。

在第三个样例中，注意如果你只在第一根藤蔓上荡动，是无法碰到第二根的——你必须在荡动时爬上一些（幸运的是，你可以这么做）才能抓住第二根。记住，你只能在荡动时向上爬，不能向下（因为向上藤蔓是拉紧的可以承重，向下则是自由荡动的）。第四个样例中，即使你能到第二根藤蔓，但它太短，无法到达终点岩架。

限制条件

• $0 < d_i, l_i, D \leq 10^9$
• $T \leq 30$
• $d_i < d_{i+1}$
• 起始时你抓住第一根藤蔓，$d_0 \leq l_0$
• $d_{N-1} < D$

测试集 1（5 分，结果可见）

• $1 \leq N \leq 100$

测试集 2（9 分，结果隐藏）

• $1 \leq N \leq 10000$
• 所有测试用例的藤蔓总数不超过 60000

翻译由 ChatGPT-4.1 完成。