Start

2020-02-10 04:15 AKST

Kattis Set 05

End

2020-02-17 00:30 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -290 days 0:06:41

Time elapsed

164:15:00

Time remaining

0:00:00

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.

Sample Input 1 Sample Output 1
2
1 10
33
54
3 10
43 10 59
69 69 69
4
1