Description

【题意】

约翰收集了 $N$ 本书，第i本书的宽度是 $W_i$ ，高度是 $H_i$ 。
约翰想做个书架来放置这套书。书架是长方形的，分为若干层，具体分多少层由约翰自由决定。
由于木料的问题，书架的宽度固定为 $L$ ，即在一层书架上的书的宽度之和不能超过 $L$ 。
既然书架的宽度是固定的，约翰想让书架的高度尽量低一点。

这些书构成一个系列，为了检索方便，书必须按照编号顺序摆放。也就是说，第一本书必须放在第一层，同层的书籍次序必须连续，如果一本书是第 $k$ 层书架上最后一本，那么下一本就必须放在第 $k+1$ 层上。

假设书架的高度就是每层书架的高度之和，每层书架的高度是该层中最高的一本书。

请问约翰应该选择一个多少层次的书架，每层书架放哪些书，才能让书架的高度最小？

【输入格式】
第一行：两个整数 $N$ 和 $L$ ，$1 \le N \le 10^5$ , $1 \le L \le 10^9$
第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数 $H_i$ 和 $W_i$ ， $1 \le H_i \le 10^6$, $1 \le W_i \le L$ 

【输出格式】
单个整数：表示书架的最低高度

【样例输入】
5 10
5 7
9 2
8 5
13 2
3 8

【样例输出】
21

【解释】
将书架做成三层，第一层放第一本，第二层放第二本到第四本，第三层放第五本

Hint

这是个**的单调队列优化，害我以为有 $O(n)$ 做法，想了半天。

线段树嗯造就完了，不要像我一样对着标题浪费时间。