Swinging Wild

You stand on a ledge in the jungle. The person you love stands on a ledge of the same height on the far side of a swamp full of snakes and crocodiles. Vines hang from the jungle canopy over the swamp, and you managed to get hold of the first of them. The canopy is at a constant height and both ledges are at that height. Each vine hangs straight down from one point of the canopy, and the vines have different lengths.

A fictional hero would swing wildly, let go in mid air, fly for a while, catch another vine, and repeat until reaching the other side. You are not a fictional hero, so your plan is slower. You swing on the vine you hold and, without letting go of it, you catch another vine. Then you climb up your original vine until the new vine hangs horizontally from its root to your hand, either along its full length or along the distance between the two roots, whichever is shorter. You rest, then swing again and repeat.

You do not have to catch the first vine your swing meets. You can swing further and catch a vine beyond it. You can also climb up the vine you are swinging on to shorten the distance to its root, so you can catch any vine that your vine crosses while swinging. You never climb down while swinging: the part of the vine above your hand is taut and carries your weight, and the part below it swings free.

Before you start, you want to know whether this method reaches the other side at all.

Put your own ledge at coordinate 0. Vine $i$ hangs from coordinate $d_i$ and has length $l_i$. While you hold vine $i$ at a point $r$ units below the canopy, your swing crosses every coordinate $x$ with $|x - d_i| \le r$, so you can catch vine $j$ whenever $|d_j - d_i| \le r$. Catching vine $j$ that way leaves you holding it $\min(l_j, |d_j - d_i|)$ units below the canopy. You start on the ledge holding vine $1$, so your first grip is $d_1$ units below the canopy. Holding vine $i$ at $r$ units below the canopy, you reach the far ledge when $d_i + r \ge D$.

The first line holds the number of test cases $T$. Each test case starts with a line holding the number of vines $N$. The next $N$ lines hold two integers $d_i$ and $l_i$, the distance of the vine's root from your ledge and the length of the vine. The last line of the test case holds the distance $D$ to the ledge where the person you love stands. You start holding vine $1$.

Constraints:

• $1 \le T \le 30$
• $1 \le N \le 10000$
• $0 < d_i, l_i, D \le 10^9$
• $d_i < d_{i+1}$
• $d_1 \le l_1$
• $d_N < D$
• The test cases hold at most $60000$ vines in total.

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is YES if you can reach the person you love and NO otherwise.

The four cases below are the first sample test.

In the first case you hold the first vine 3 units from the point where it is attached. You swing, pass the second vine, and just barely catch the third one. The picture shows the starting position. You can catch any vine rooted inside the red interval.

After resting you climb down the third vine and up the first one, so you end up 3 units from the start, touching the canopy and holding the first and third vines. You let go of the first vine, swing again, and just barely reach the ledge where the person you love waits. The second picture shows the position after you caught the third vine and climbed over to the root of the first one, again with the reachable interval in red.

In the second case the first swing does not reach the third vine, so your only choice is the second one. Its root is 4 units from the start, so climbing up the first vine gives you only 1 unit of swing, far too little for the third vine. You never even reach the third vine.

In the third case a plain swing on the first vine does not cross the second one. You have to climb up a little while swinging, which is allowed. Climbing up is the only direction you can go while swinging, because the vine above your hand is taut and the vine below it swings free.

In the fourth case you can catch the second vine, but it is too short to reach the final ledge.