27952번 - 보디빌딩 서브태스크

건표는 헬스를 좋아하는 사람이다. 건표는 자신만의 운동 루틴이 있다. 건표는 이 루틴을 진행할 때마다 몸무게가 $X$ kg만큼 빠졌다. 건표는 하루에 몇 번이고 이 루틴을 진행할 수 있었다.

건표는 장차 있을 보디빌딩 대회를 위해 $N$일에 걸쳐 식단을 짜놓았다. 이 계획에 의하면 $i$번째 날에는 건표의 몸무게가 $B_i$ kg만큼 찐다. 다만, 건표가 운동을 하다가 쓰러지면 안 되기 때문에 $i$번째 날에 최종 몸무게가 최소 $A_i$ kg 이상이 되길 원했다. 만약 건표가 너무 많이 운동을 하거나 너무 적게 음식을 먹어서 그날에 최종적으로 $A_i$ kg보다 적은 몸무게를 가진다면, 건표는 그 자리에서 쓰러진다. 건표는 보디빌딩 대회에서 우승하기 위해 루틴을 최대한 많이 진행하여 최대한 건강한 몸을 만들고 싶었다. 건표가 쓰러지지 않는 선에서 이 루틴을 최대 몇 번까지 진행할 수 있는지 구하여라.

첫째 줄에는 두 정수 $N$과 $X$가 주어진다. $N$은 보디빌딩 대회까지 남은 일수. $X$는 루틴을 진행할 때마다 빠지는 몸무게(kg)이다.

둘째 줄에는 $N$개의 정수 $A_i$가 주어진다. $i$번째 정수 $A_i$는 $i$번째 날 최종 몸무게의 하한을 의미한다.

셋째 줄에는 $N$개의 정수 $B_i$가 주어진다. $i$번째 정수 $B_i$는 $i$번째 날에 늘어나는 몸무게를 나타낸다.

첫째 줄에 건표가 쓰러지지 않고 진행할 수 있는 최대 루틴 수를 출력한다.

만약 어떻게 하더라도 $N$일 이내에 건표가 쓰러진다면 -1을 출력하라.

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