768. [USACO Open12] 书架

【题目描述】

当约翰不挤牛奶，不堆干草包，不把牛排成一排或者重新修建围栏时，他喜欢坐下来读一本好书。

这么多年来，他收集了 N本书，他想建造一套新的书架来放置它们。

每本书 ii 都有一个宽度 Wi 和高度 Hi。

书籍需要按照顺序放置到这套书架中。

例如，第一个书架应放置书 1..k（对于某个 k），第二个书架放置的书应从 k+1开始，以此类推。

每个架子的总宽度最多为 L。

单个书架的高度等于该书架中最高的书的高度，整套书架的高度等于所有单个书架的高度和，因为它们是垂直堆叠的。

请帮助约翰计算整套书架的最小可能高度。

【输入格式】

第一行包含两个整数 N 和 L。

接下来 N行，每行包含两个整数 Hi 和 Wi。

【输出格式】

输出整套书架的最小可能高度。

【样例输入】

5 10

5 7

9 2

8 5

13 2

3 8

【样例输出】

21

【样例解释】

共 5 本书，每个书架的最大宽度为 10。

一种最佳放置方式为建造 33 个书架，第 1个书架放置书 1，第 2 个书架放置书 2,3,4，第 3 个书架放置书 5。

总高度为 5+13+3=21。

【数据范围】

$1\leq N\leq 2000$

$1\leq L \leq 10^9$

$1\leq Hi\leq 10^6$

$1\leq Wi \leq L$

【来源】

USACO 2012 US Open Silver Division