플래그 대사 그만 좀 말해요

시간 제한1초메모리 제한1024 MB

요약

한 지점에서 외치면 오른쪽 i칸 떨어진 부하가 max(0, K-i)만큼 강해질 때, 모든 부하가 목표 이상이 되도록 하는 최소 외침 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 슬라이딩 윈도우, 누적 합
정답자: 아직 제출이 없습니다

문제

“해치웠나?”

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

부하들은 좌우 방향의 직선 위에 $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$

예제2

예제 1
입력
```
2 3
3 6
6 10
```
예상 출력
```
2
```
예제 2
입력
```
2 3
10 10
2 3
```
예상 출력
```
0
```