Problem M
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\le 100$ giving the number of test cases. Each test case has three lines. On the first line, there are two integers $N$ ($1\le N\le 10000$), the number of buildings, and $D$ ($1\le D\le {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\le H_i\le {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\le E_i\le {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