전력 평준화

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

요약

매일 저수지의 물을 얼마나 전기로 바꿀지 정해, 하루 발전량의 최댓값과 최솟값 차이가 가장 작아지도록 하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 그리디, 투 포인터, 누적 합
정답자: 아직 제출이 없습니다

문제

한 마을은 모든 전기를 태양광 발전과 수력 발전을 하는 댐에서 얻는다. 햇빛과 물의 양은 날마다 크게 달라질 수 있어서 이 에너지원들은 늘 믿을 만하지는 않다. 다행히 댐에는 큰 저수지가 있어서 물을 저장해 날마다 공급되는 전기를 고르게 맞출 수 있다.

문제

앞으로 올 $n$ 일에 대한 정보가 주어진다. $i$ 번째 날에 태양광 발전소는 $s_i$ 만큼의 전기를 생산한다. 같은 날 $w_i$ 만큼의 물이 저수지로 흘러 들어온다. 물 1단위는 전기 1단위로 바꿀 수 있으며, 얼마를 전기로 바꾸고 얼마를 저수지에 남길지 정할 수 있다. 다만 저수지는 최대 $r$ 단위의 물만 담을 수 있으므로, 하루가 끝난 뒤 저수지의 물은 $r$ 을 넘을 수 없다. 첫째 날을 시작할 때 저수지는 비어 있다.

첫째 날에는 저수지에 저장된 물이 없다. 마지막 날이 끝나면 댐은 점검을 받아야 하므로 저수지가 반드시 비어 있어야 한다. 즉, $n$ 일 동안 댐으로 흘러 들어온 물은 모두 어느 시점에서든 전기로 바뀌어야 한다.

$e_i$ 를 $i$ 번째 날에 생산된 전기량이라 하자. 그러면 $e_i = s_i + r_i$ 이며, 여기서 $r_i$ 는 $i$ 번째 날에 저수지에서 전기로 바꾼 물의 양이다. 목표는 $\max_i(e_i) - \min_i(e_i)$ 의 최솟값을 구하는 것이다.

입력

첫 줄에 날의 수 $n$ 과 저수지가 담을 수 있는 물의 양 $r$ 이 정수로 주어진다 ( $1 \leq n \leq 10^5$ , $1 \leq r \leq 10^9$ ). 이어지는 $n$ 개의 줄에는 각각 두 정수 $s_i$ 와 $w_i$ 가 주어진다 ( $0 \leq s_i, w_i \leq 10^9$ ). $s_i$ 는 $i$ 번째 날 태양광 발전소가 생산한 전기량이고, $w_i$ 는 같은 날 저수지로 흘러 들어온 물의 양이다.

출력

$\max_i(e_i) - \min_i(e_i)$ 의 최솟값을 출력한다.

예제1

예제 1
입력
```
3 1
4 2
2 0
5 1
```
예상 출력
```
3
```