책장

농부 존은 소젖을 짜거나, 건초 더미를 쌓거나, 소를 줄 세우거나, 울타리를 만들지 않을 때면 좋은 책과 함께 앉아 있는 것을 즐긴다. 여러 해에 걸쳐 그는 책 $N$권을 모았고($1 \le N \le 2,000$), 이 책들을 모두 꽂을 새 책장을 만들려고 한다.

각 책 $i$에는 너비 $W_i$와 높이 $H_i$가 있다. 책은 주어진 순서대로 여러 칸(선반)에 차례로 꽂아야 한다. 예를 들어 첫째 칸에는 책 $1 \dots k$가, 둘째 칸에는 책 $k+1$부터가 들어가는 식이다. 한 칸에 꽂힌 책들의 너비 합은 최대 $L$까지만 허용된다($1 \le L \le 10^9$). 한 칸의 높이는 그 칸에 놓인 가장 높은 책의 높이와 같고, 모든 칸을 세로로 쌓아 올리므로 책장 전체의 높이는 각 칸 높이의 합이 된다.

책장 전체의 높이를 최소로 만들 때, 그 최소 높이를 구하라.

• 첫째 줄: 두 정수 $N$과 $L$이 공백으로 구분되어 주어진다.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 책 $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$(높이 13, 너비 합 9)가 놓이며, 셋째 칸에는 책 5(높이 3, 너비 8)가 놓인다.