Swinging Wild (Small)

You are standing on a ledge at the edge of a jungle swamp, and the person you love is standing on another ledge on the far side. The swamp is full of snakes and crocodiles, so wading across is out of the question. Vines hang from the jungle canopy over the swamp, and you already have hold of the first one.

The canopy is at a constant height, and both ledges are level with it. Vine $i$ hangs straight down from the point at distance $d_i$ from your ledge and has length $l_i$. You start on your ledge holding vine $0$, so you grip it $d_0$ units from the point where it is attached.

You will not let go and fly through the air the way a fictional hero would. Holding a vine $r$ units from its attachment point and swinging back and forth, the taut vine sweeps a half disc of radius $r$ below the canopy. While swinging you may climb up, which makes $r$ smaller, but you may not climb down. If vine $j$ is attached within distance $r$ of the attachment point of the vine you hold, you can catch vine $j$. After catching it you climb up your original vine until the new vine is horizontal, so your new grip distance on vine $j$ is the smaller of $l_j$ and the distance between the two attachment points. You rest for a bit and then swing again.

You do not have to catch the first vine you meet while swinging; you may swing past it and take a farther one instead. Holding a vine attached at $d_i$ with grip distance $r$, you reach the other ledge when $d_i + r \ge D$, where $D$ is the distance to that ledge.

Decide whether you can cross the swamp this way.

The first line contains the number of test cases $T$. The first line of each test case contains the number of vines $N$. The next $N$ lines each contain two integers $d_i$ and $l_i$, the distance of the attachment point from your ledge and the length of the vine. The last line of the test case contains the distance $D$ to the other ledge. You start by holding the first vine.

The constraints are the following.

• $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$

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

In the first sample case you hold the first vine 3 units from its attachment point. You swing wide, pass the second vine, and just barely catch the third one. The picture below shows the starting situation, and you can catch any vine attached inside the red interval.

After resting, you climb down the third vine and up the first one, ending three units from the start at canopy height, holding the first and the third vine. You let go of the first vine, swing again, and just barely reach the ledge where the person you love is waiting. The picture below shows the situation after you caught the third vine and moved over to the attachment point of the first one. Again, any vine attached inside the red interval is within reach.

In the second sample case the first swing does not reach the third vine, so your only choice is to catch the second one. It is attached four units from the start, so climbing up the first vine leaves you only one unit of swing, which is far too little to reach the third vine. You cannot even get to the third vine, let alone the other side of the swamp.

In the third sample case, swinging on the first vine at full length takes your hands below the bottom end of the second vine. The vine you hold still crosses the second one, and climbing up a little while swinging lets you catch it. You can only climb up, never down: the part of the vine above your hands is taut and carries your weight, while the part below your hands swings free.

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