Problem K
City Destruction

Modan is playing a new action strategy game, where his goal is to destroy a city.

A city is made up of $N$ buildings, where the $i$-th building initially has health $H_ i$. At every move, Modan can choose a building to attack, dealing $D$ damage to it. When a building’s health falls below or equal to $0$, it is destroyed. When the $i$-th building gets destroyed, it explodes and deals $E_ i$ damage to the adjacent buildings, i.e. the $i-1$-th and $i+1$-th buildings, if they exist.

Modan is really addicted to the game and wants to know the minimum number of moves he needs to destroy a city.

Input

The first line contains a single integer $T \leq 100$ giving the number of test cases. Each test case has three lines. On the first line, there are two integers $N$ ($1 \leq N \leq 10\, 000$), the number of buildings, and $D$ ($1 \leq D \leq 10^9$), the amount of damage Modan can do. On the second line, there are $N$ integers, with the $i$-th integer being $H_ i$ ($1 \leq H_ i \leq 10^9$), the initial health of the $i$-th building. On the third line, there are $N$ integers, with the $i$-th integer being $E_ i$ ($0 \leq E_ i \leq 10^9$), the amount of explosion damage the $i$-th building does.

Output

For each test case, output a single line containing the minimum number of moves needed to destroy the city.

2
1 10
33
54
3 10
43 10 59
69 69 69

4
1