[USACO12OPEN] Bookshelf S

题目描述

Farmer John 闲来无事的时候总喜欢坐下来看书。这些年来,他一共收集了 $N$ 本书($1 \leq N \leq 2000$),他打算搭一个新的书架来装这些书。 每本书都有个宽度 $w_i$ 和高度 $h_i$,书必须按顺序来摆放(即同一层书架摆的书必须是连续的一个区间)。每层书架的总宽度不能超过 $L$($1 \leq L \leq 10^9$),每层书架的高度等于这一层最高的书的高度,整个书架的高度等于每层书架的高度之和。 现在请你帮 FJ 求出书架高度的最小值。

输入输出格式

输入格式


第一行两个整数 $N,L$。 接下来 $N$ 行,每行两个整数 $h_i,w_i$($1 \leq h_i \leq 10^6$,$1 \leq w_i \leq L$)。

输出格式


输出一个整数,书架高度最小值。

输入输出样例

输入样例 #1

5 10
5 7
9 2
8 5
13 2
3 8

输出样例 #1

21

说明

第一层放第一本书,第二层放第二,三,四本书,第三层放第五本书,总高度为 $5+13+3=21$,可以证明不存在更优的方案。