你正站在丛林的一处岩架上，而你的真爱站在沼泽另一侧的类似岩架上。沼泽中布满了蛇、鳄鱼和其他各种令人不快的生物。幸运的是，丛林树冠上垂下了许多藤蔓，更幸运的是，你不知怎么设法抓住了第一根藤蔓（见下图）。丛林树冠的高度是恒定的，两个岩架的高度也与树冠高度相同。藤蔓只是从树冠特定点垂下的线，长度各不相同。

如果你是一个虚构的英雄，你会疯狂地摆动并大喊大叫，在某个时刻松开手中的藤蔓，在空中飞行一段时间，抓住另一根藤蔓，再次摆动，重复几次后，你就能将你的真爱拥入怀中。不幸的是，你不是虚构的英雄，如果你尝试那样做，可能唯一能做好的就是大喊大叫。

你的计划要谨慎得多。你将在你持有的藤蔓上摆动，但不会松手，而是去抓住另一根藤蔓。然后，你将缓慢而小心地向上攀爬你最初持有的藤蔓，使得你抓住的新藤蔓变平——达到其全长，或者达到两根藤蔓之间的距离，取两者中的较小值。然后你休息一会儿，再次摆动，重复这个过程。注意，你在摆动时不必抓住遇到的第一根藤蔓，你可能更喜欢摆动得更远一点，去抓住更远处的藤蔓。你也可以在你当前摆动的藤蔓上向上攀爬，以缩短你与藤蔓根部之间的距离。实际上，这意味着你可以抓住你在摆动过程中经过的任何藤蔓。注意，你在摆动时不会向下攀爬藤蔓。

让你与任何虚构英雄不同的另一件事是，在开始整个相当冒险的过程之前，你想知道是否真的有可能通过这种方式到达丛林的另一侧。这就是你在本题中需要回答的问题。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含藤蔓的数量 $N$。接下来 $N$ 行描述藤蔓，每行包含一对整数 $d_i$ 和 $l_i$，分别表示藤蔓距离你所在岩架的距离以及藤蔓的长度。测试用例的最后一行包含到达你真爱所在岩架的距离 $D$。你开始时手中持有第一根藤蔓。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是 YES 或 NO，表示根据上述规则，你是否能够到达你的真爱所在处。

数据范围

内存限制：1GB。

时间限制：8 秒。

$0 < d_i, l_i, D \le 10^9$。

$T \le 30$。

$d_i < d_{i+1}$。

由于你持有第一根藤蔓，$d_0 \le l_0$。

$d_{N-1} < D$。

子任务 1

$1 \le N \le 100$。

子任务 2

$1 \le N \le 10000$。

所有测试用例中的藤蔓总数不超过 60000。

样例

输入 1

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

输出 1

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

说明

在第一个案例中，你持有距离起点 3 个单位的藤蔓。你疯狂摆动，绕过第二根藤蔓，勉强抓住了第三根。下图描绘了初始情况，你可以到达任何根部位于红色区间内的藤蔓：

休息后，你从第三根藤蔓向下爬，并向上爬第一根藤蔓，发现自己距离起点 3 个单位，触碰到了树冠并同时抓住了第一根和第三根藤蔓。现在你松开第一根藤蔓，再次摆动，刚好勉强到达你的真爱所在的岩架。下图描绘了你抓住第三根藤蔓并爬到第一根藤蔓根部后的情况。同样，你可以到达任何根部位于红色区间内的藤蔓：

在第二个案例中，你在第一次摆动时无法到达第三根藤蔓，所以你唯一的选择是抓住第二根。然而，由于它距离起点 4 个单位，你（通过向上爬第一根藤蔓）只能给自己 1 个单位的摆动距离——显然不足以到达第三根藤蔓。因此，你甚至无法到达第三根藤蔓，更不用说沼泽的另一侧了。最好去找找别的路（或者寻找新的真爱）。

在第三个案例中，请注意，如果你只是在你持有的第一根藤蔓上摆动，你的路径不会与第二根藤蔓相交——你必须在摆动时向上爬一点（幸运的是，你可以这样做）才能到达第二根藤蔓。记住，你在摆动时只能向上爬，不能向下爬（因为向上爬的藤蔓是绷紧的，你可以把重量压在上面，而向下爬的藤蔓是自由摆动的）。在第四个案例中，尽管你可以到达第二根藤蔓，但它太短了，无法到达最终的岩架。