Bodybuilding

Geonpyo likes working out at the gym and has his own exercise routine. Each time he completes the routine, his body weight drops by $X$ kg. He can run the routine as many times as he likes in a single day.

Geonpyo prepared a meal plan for the next $N$ days ahead of a bodybuilding competition. On day $i$, the plan adds $B_i$ kg to his weight. However, he must not collapse during training, so his final weight on day $i$ must be at least $A_i$ kg. If he trains too much or eats too little so that his final weight on some day is less than $A_i$ kg, he collapses on the spot. Geonpyo wants to win the competition, so he wants to run the routine as many times as possible to build the healthiest body he can. Find the maximum number of times he can run the routine without collapsing.

The first line has two integers $N$ and $X$. $N$ is the number of days left until the competition, and $X$ is the weight in kg lost each time the routine is run.

The second line has $N$ integers $A_i$. The $i$-th integer $A_i$ is the lower bound on his final weight on day $i$.

The third line has $N$ integers $B_i$. The $i$-th integer $B_i$ is the weight gained on day $i$.

Print the maximum number of routine runs Geonpyo can complete without collapsing.

If he collapses within $N$ days no matter what he does, print -1.

• $1 \leq N \leq 500,000$
• $1 \leq A_i, B_i, X \leq 1,000,000,000$ ($1 \leq i \leq N$)