시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

3 초 | 256 MB | 41 | 10 | 10 | 38.462% |

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,

- P
_{i}be the i’th pad (1 <= i <= n), P_{0}be the left end and P_{n+1}be the right end. - r
_{i}be the length of the rope R_{i}between P_{i}and P_{i+1}(for 0 <= i <= n). - p
_{i}be the position of P_{i}(0 <= i <= n + 1). Obviously p_{0}= 0, p_{n+1}= L and p_{i}< p_{i+1}, r_{i}>= p_{i+1}- p_{i}(for 0 <= i <= n).

When Joey is on P_{i} he can pull R_{i} and then P_{i+1} moves towards Joey. If the rope R_{i+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 P_{i+2} and P_{i+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 P_{n+1} then there is no movements of the pads at all (since the right end is fixed, that is P_{n+1} is not movable). Let’s try to clarify these statements by some examples.

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

Example 2: Let Joey is on P_{0} and n = 1. Position of the only lily pad P_{1} is at p_{1} = 10. Let pond length L = 20. By definition p_{0} = 0 and p_{2} = L = 20. Also let’s assume r_{0} = 10, r_{1} = 11. If Joey pulls R_{0} by one unit then: p_{1} = 9. But now R_{1} is taut. If he pulls R_{0} more P_{1} will not move, because the rope between P_{1} and P_{2} is taut and P_{2} 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.

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: p_{0}, p_{1}, … p_{n+1}. Third line contains n + 1 positive integers r_{0}, r_{1} … r_{n}. 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.

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

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

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