Problem L
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 |