책장

면접 대비

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

요약

책을 순서대로 너비 합이 L 이하인 선반들로 나누어 각 선반 최대 높이의 합을 최소로 만든다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 세그먼트 트리, 스택
정답자: 아직 제출이 없습니다

문제

농부 John이 $N$ 권( $1 \le N \le 100000$ )의 책을 모았고, 이 책들을 모두 꽂을 책장을 만들려고 합니다.

각 책 $i$ 에는 너비 $W(i)$ 와 높이 $H(i)$ 가 있습니다. 책은 반드시 순서대로 선반에 꽂아야 합니다. 즉, 첫 번째 선반에는 어떤 $k$ 에 대해 책 $1 \dots k$ 가 꽂히고, 두 번째 선반은 책 $k+1$ 부터 시작하며, 이런 식으로 이어집니다. 한 선반에 꽂힌 책들의 너비 합은 최대 $L$ ( $1 \le L \le 10^9$ )까지 가능합니다.

한 선반의 높이는 그 선반에 꽂힌 책 중 가장 높은 책의 높이와 같고, 책장 전체의 높이는 모든 선반의 높이를 더한 값입니다(선반들은 세로로 쌓여 있습니다).

책장 전체의 높이가 될 수 있는 최솟값을 구하세요.

입력

첫째 줄에 두 정수 $N$ 과 $L$ 이 공백으로 구분되어 주어집니다.

다음 $N$ 개의 줄 중 $i$ 번째 줄에는 책 $i$ 의 높이 $H(i)$ 와 너비 $W(i)$ 가 공백으로 구분되어 주어집니다( $1 \le H(i) \le 10^6$ , $1 \le W(i) \le L$ ).

출력

책장 전체의 높이가 될 수 있는 최솟값을 한 줄에 출력하세요.

설명

첫 번째 예제에서는 책이 $5$ 권 있고, 각 선반의 너비 합은 최대 $10$ 까지 가능합니다. 최적의 배치 중 하나는 선반 $3$ 개를 사용합니다. 첫 번째 선반에는 책 $1$ (높이 $5$ , 너비 $7$ )만, 두 번째 선반에는 책 $2 \dots 4$ (높이 $9, 8, 13$ 이므로 선반 높이는 $13$ , 너비 합은 $9$ ), 세 번째 선반에는 책 $5$ (높이 $3$ , 너비 $8$ )를 꽂습니다. 전체 높이는 $5 + 13 + 3 = 21$ 입니다.

예제3

예제 1
입력
```
5 10
5 7
9 2
8 5
13 2
3 8
```
예상 출력
```
21
```
예제 2
입력
```
1 5
1000000 3
```
예상 출력
```
1000000
```
예제 3
입력
```
6 6
4 3
1 3
6 2
2 4
5 1
3 5
```
예상 출력
```
15
```