점프하는 개구리 조이

개구리 조이는 집 옆에 있는 긴 연못을 건너려고 한다. 연못은 길이가 $L$인 선분이고, 그 위에 연잎 $n$개가 놓여 있다. 연잎에는 왼쪽부터 1번, 2번, 순서대로 번호를 붙인다. 조이는 연못의 왼쪽 끝에서 출발해 1번 연잎, 2번 연잎을 차례로 밟고, 마지막에는 $n$번 연잎에서 오른쪽 끝으로 건너간다. 뒤로 돌아갈 수는 없다.

이동 방법은 점프와 헤엄 두 가지다. 두 지점 사이의 거리가 $D$ 이하이면 점프할 수 있고, 헤엄은 거리에 상관없이 몇 번이든 할 수 있다. 조이는 몸이 젖는 것을 싫어하므로 헤엄치는 횟수를 최소로 줄이려고 한다.

인접한 두 지점 사이에는 모두 밧줄이 하나씩 묶여 있다. 왼쪽 끝과 1번 연잎 사이, 인접한 두 연잎 사이, $n$번 연잎과 오른쪽 끝 사이가 모두 여기에 해당한다.

기호는 다음과 같이 쓴다.

1. $P_i$는 $i$번 연잎이고 ($1 \le i \le n$), $P_0$은 왼쪽 끝, $P_{n+1}$은 오른쪽 끝이다.
2. $r_i$는 $P_i$와 $P_{i+1}$을 잇는 밧줄 $R_i$의 길이다 ($0 \le i \le n$).
3. $p_i$는 $P_i$의 위치다 ($0 \le i \le n+1$). $p_0 = 0$, $p_{n+1} = L$이고, $p_i < p_{i+1}$, $r_i \ge p_{i+1} - p_i$가 성립한다.

조이가 $P_i$ 위에 있을 때 밧줄 $R_i$를 당기면 $P_{i+1}$이 조이 쪽으로 끌려온다. 이때 밧줄 $R_{i+1}$이 팽팽하면, 즉 밧줄의 길이가 그 밧줄이 잇는 두 연잎 사이의 거리와 같으면 $P_{i+2}$도 함께 끌려오고, 그다음 밧줄도 팽팽하면 같은 방식으로 계속 이어진다. 팽팽하지 않은 밧줄에서는 움직임이 더 전달되지 않는다. 오른쪽 끝 $P_{n+1}$은 고정되어 있으므로 $P_{n+1}$까지 밧줄이 모두 팽팽해지면 연잎은 전혀 움직이지 않는다. 밧줄을 아무리 당겨도 연잎이 조이가 서 있는 위치보다 왼쪽으로 가지는 않는다.

예 1. 조이가 $P_2$ 위에 있고 $p_2 = 10$, $p_3 = 20$, $p_4 = 30$, $p_5 = 40$, $r_2 = r_3 = r_4 = 15$라고 하자. $P_2$와 $P_3$, $P_3$과 $P_4$, $P_4$와 $P_5$ 사이의 거리는 모두 10인데 밧줄 길이는 15이므로 팽팽한 밧줄이 하나도 없다. 조이가 $R_2$를 1만큼 당기면 $P_3$이 1만큼 다가와 $p_3 = 19$가 된다. $R_3$이 팽팽하지 않았으므로 $P_4$는 움직이지 않는다. 여기서 4만큼 더 당기면, 즉 모두 5만큼 당기면 $p_3 = 15$, $p_4 = 30$, $p_5 = 40$이 된다. 이제 $p_4 - p_3 = 15 = r_3$이므로 $R_3$이 팽팽해진다. 1만큼 더 당기면 $P_3$과 $P_4$가 함께 움직여 $p_3 = 14$, $p_4 = 29$가 되고, $R_4$는 아직 팽팽하지 않으므로 $p_5 = 40$ 그대로다.

예 2. 조이가 $P_0$에 있고 $n = 1$, $p_1 = 10$, $L = 20$이라고 하자. 정의에 따라 $p_0 = 0$, $p_2 = 20$이다. 여기에 $r_0 = 10$, $r_1 = 11$이라고 하자. 조이가 $R_0$을 1만큼 당기면 $p_1 = 9$가 되고, $P_1$과 $P_2$ 사이의 거리가 11이 되어 $R_1$이 팽팽해진다. 이 상태에서 $R_0$을 더 당겨도 $P_2$는 오른쪽 끝이라 고정이므로 $P_1$은 더 이상 움직이지 않는다.

조이가 왼쪽 끝에서 오른쪽 끝까지 가는 동안 몸을 적셔야 하는 최소 횟수를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($T \le 50$)가 주어진다. 각 테스트 케이스는 세 부분으로 이루어진다.

첫 부분에는 두 양의 정수 $n$ ($n \le 1000$)과 $D$ ($D \le 10^9$)가 주어진다. 둘째 부분에는 정수 $n + 2$개 $p_0, p_1, \dots, p_{n+1}$이 주어진다. 셋째 부분에는 양의 정수 $n + 1$개 $r_0, r_1, \dots, r_n$이 주어진다. $p_i$와 $r_i$는 모두 $10^9$ 이하다.

입력으로 주어지는 값은 모두 문제에서 설명한 조건을 만족한다. 인접한 수 사이나 줄 사이에는 공백이나 줄바꿈이 하나 이상 올 수 있다.

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 조이가 헤엄쳐야 하는 최소 횟수다.