AR2015PF - Jumping Joey

no tags 

Please read the problem statement carefully. Mathematical notations and bunch of examples are provided to make the statement friendly.

Once upon a time, there lived a frog named Joey. He has a long pond beside his house. There are lots of lily pads there, and he likes to jump from one pad to another. He hates to wet himself. Let’s help Joey to cross the pond. For the sake of simplicity, let’s assume the pond to be a line segment of length L. On this line segment there are n lily pads. Let’s enumerate the lily pads from left to right, that is the leftmost pad is number 1, second one from the left is number 2 and so on. At the beginning Joey is at the left end of the pond. Then he moves to the first pad, then to the second pad and so on. At the end he moves from the nth pad to the right end of the pond. There are two ways he can move, jump and swim. He can jump from one place to another if the distance between these two places is no more than D unit. He can swim any times he wants. But as we already said he does not like to wet himself, so we need to minimize the number of times he swims for going from the left end to the right end.

However, the situation is not that simple. There are ropes between every two adjacent places. That is, there is rope between:

  • Left end and first pad.
  • Last pad and right end.
  • Between every two adjacent pads.

Let,

  • Pi be the i’th pad (1 <= i <= n), P0 be the left end and Pn+1 be the right end.
  • Ri be the length of the rope Ri between Pi and Pi+1 (for 0 <= i <= n).
  • Pi be the position of Pi (0 <= i <= n + 1). Obviously P0 = 0, Pn+1 = L and Pi < Pi+1, Ri >= Pi+1 - Pi (for 0 <= i <= n).

When Joey is on Pi he can pull Ri and then Pi+1 moves towards Joey. If the rope Ri+1 is taut (the length of the rope is equal to the distance between the two pads that the rope is tied with) then this also affects Pi+2 and Pi+2 moves toward him as well (and so on). However, if a rope is not taut then it does not affect later pads. Also if the ropes are taut till Pn+1 then there is no movements of the pads at all (since the right end is fixed, that is Pn+1 is not movable). Let’s try to clarify these statements by some examples.

Example 1

Let Joey be on P2, P2 = 10, P3 = 20, P4 = 30, P5 = 40. Also R2 = R3 = R4 = 15. Distance between P2-P3, P3-P4 and P4-P5 are 10, but the rope lengths are 15. So none of the ropes are taut. Now if Joey pulls R2 say by 1 unit, P3 will shift one unit towards P2 (new P3 = 19). But this does not affect P4, because R3 was not taut. Let Joey pulls rope R2 4 more units (5 units in total). Then P3 = 15, P4 = 30, P5 = 40. Now R3 becomes taut since P3-P4 distance is now: P4 - P3 = 30 - 15 = 15 which is same as R3. So now, if Joey pulls one more unit, P3 and P4 moves together (P5 does not, since R4 is not taut). So the new positions would be: P3 = 14, P4 = 29, P5 = 40.

Example 2

Let Joey be on P0 and n = 1. Position of the only lily pad P1 is at P1 = 10. Let pond length L = 20. By definition P0 = 0 and P2 = L = 20. Also let’s assume R0 = 10, R1 = 11. If Joey pulls R0 by one unit then: P1 = 9. But now R1 is taut. If he pulls R0 more P1 will not move, because the rope between P1 and P2 is taut and P2 is the right end.

Given all the information, you have to figure out minimum number of times Joey has to wet himself in order to go from the left end to the right end. Please note Joey has to move from one place to the next place (he can’t move backward), so he can’t just wet himself once and swim from the left end to the right end.

Input

First line of the input will be a positive integer T (<= 50), number of test cases. Test cases are separated by blank lines. Each case consists of 3 lines. First line contains two positive integers n (<= 1,000) and D (<= 10^9). Second line contains n + 2 integers: P0, P1 ... Pn+1. Third line contains n + 1 positive integers R0, R1 ... Rn. None of the Pi and Ri will be more than 10^9. You may assume that all of these given values will satisfy all the constraints in the statement. Please note there may be one or more spaces/new lines separating adjacent lines/numbers.

Output

For each of the tests print the case number and the answer.

Example

Input:
5
1 10
0 10 20
10 10

1 10
0 11 20
11 10

1 10
0 11 20
11 9

1 5
0 10 20
20 20

1 5
0 10 20
20 12

Output:
Case 1: 0
Case 2: 0
Case 3: 1
Case 4: 1
Case 5: 2


Added by:Gầy :))
Date:2016-07-09
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:The 2015 ACM-ICPC Asia Phuket Regional Programming Contest