27450번 - 플래그 대사 그만 좀 말해요

“해치웠나?”

악의 단체의 리더 한별이는 자신의 부하들이 “해치웠나?”라는 말을 들을 때마다 강해지는 것을 보고 이를 악용해 부하들을 강화시켜 세계를 정복하려고 한다.

부하들은 좌우 방향의 직선 위에 $1$의 간격을 두고 서 있고, 왼쪽으로부터 $i$번째에 있는 부하는 현재 강함 수치 $p_i$를 가지고 있으며 강함 수치 $t_i$를 목표로 하고 있다.

한별이는 부하들을 강화시키기 위해 어떤 지점에서 오른쪽을 보고 “해치웠나?”라는 대사를 말하는데, 이 때문에 한별이가 대사를 말하는 지점과 그 오른쪽에 있는 부하들은 한별이의 목소리를 듣고 강해진다. 그러나, 거리가 멀어질수록 한별이의 대사를 듣기 어렵기 때문에, 한별이의 목소리의 크기가 $K$일 때, 한별이가 서 있는 지점에서 오른쪽으로 $i$ ($i \ge 0$) 칸 떨어진 지점의 부하는 $\max(0,K-i)$ 만큼 강해진다.

한별이가 목이 쉬는 것을 막기 위해서, 한별이가 대사를 외치는 횟수를 최소화하려고 한다. 한별이가 최소 몇 번 대사를 말해야 부하들이 모두 목표 이상으로 강해지는지 구하시오.

첫 번째 줄에 부하의 수 $N$과 한별이의 목소리의 크기 $K$가 주어진다.

두 번째 줄에 $N$명의 부하들의 현재 강함 $p_i$가 가장 왼쪽의 부하부터 공백을 사이에 두고 주어진다.

세 번째 줄에 $N$명의 부하들의 목표 강함 $t_i$가 가장 왼쪽의 부하부터 공백을 사이에 두고 주어진다.

첫 번째 줄에 한별이가 부하들을 모두 목표 수치 이상으로 강화시키기 위하여 필요한 외침의 최소 횟수를 출력한다.

• $1 \le N \le 500\,000$
• $1 \le K \le 500\,000$
• $0 \le p_i \le 10^9$
• $0 \le t_i \le 10^9$