题目描述

When Farmer John isn't milking cows, stacking haybales, lining up his cows, or building fences, he enjoys sitting down with a good book. Over the years, he has collected N books (1 <= N <= 100,000), and he wants to build a new set of bookshelves to hold them all.

Each book i has a width W(i) and height H(i). The books need to be added to a set of shelves in order; for example, the first shelf should contain books 1...k for some k, the second shelf should start with book k+1, and so on. Each shelf can have a total width of at most L (1 <= L <= 1,000,000,000). The height of a shelf is equal to the height of the tallest book on that shelf, and the height of the entire set of bookshelves is the sum of the heights of all the individual shelves, since they are all stacked vertically.

Please help FJ compute the minimum possible height for the entire set of bookshelves.

输入格式

第一行：两个数 $N$ 和 $L$ 。

接下来 $N$ 行每行两个数 $H_i$ 和 $W_i$ 。

输出格式

一个数，书架高度的最小值。

题目大意

当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 $N$ 本书 $(1 \le N \le 100,000)$ ， 他想造一个新的书架来装所有书。

每本书 $i$ 都有宽度 $W_i$ 和高度 $H_i$ 。书需要按顺序添加到一组书架上；比如说，第一层架子应该包含书籍 $1 ... k$ ，第二层架子应该以第 $k + 1$ 本书开始，以下如此。每层架子的总宽度最大为 $L(1 \le L \le 1,000,000,000)$ 。每层的高度等于该层上最高的书的高度，并且整个书架的高度是所有层的高度的总和，因为它们都垂直堆叠。

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

有 $N(1 \le N \le 100,000)$ 本书，每本书有一个宽度 $W_i$ ，高度 $H_i$ ，$(1 \le H_i \le 1,000,000; 1 \le W_i \le L)$ 。

现在有足够多的书架，书架宽度最多是 $L (1 \le L \le 1,000,000,000)$ ，把书按顺序 $($先放 $1$ ，再放 $2.....)$ 放入书架。某个书架的高度是该书架中所放的最高的书的高度。

将所有书放入书架后，求所有书架的高度和的最小值。

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

21