题目描述

现在有 $n$ 本书排成一列，第 $i$ 本宽 $w_i$，高 $h_i$，本题中可以视为二维。

现在你需要将这一列书分为若干个区间并一层层的垒在书架中，使得每个区间的宽度之和不超过 $L$，书架的高度即为每个区间最高的树的高度之和。

现在你需要输出书架的最小高度。

形式化的，你需要确定一个序列 $p_0=1\le p_1< p_2<p_3<\dots<p_m< n+1=p_{m+1}$， 使得 $\sum\limits_{i=p_i}^{p_{i+1}-1}w_i\le L$ 始终成立并最小化 $\sum\limits_{i=0}^m\max\limits_{i=p_i}^{p_{i+1}-1}h_i$

输入格式

第一行两个整数 $n$ 和 $L$，表示书的个数和每个区间的最大宽度。

接下来 $n$ 行，每行两个整数表示 $h_i$ 和 $w_i$.

输出格式

一行一个整数，表示书架最小高度。

样例

Input # 1

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

Output # 1

21

数据范围与提示

样例解释：

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

对于 $10\%$ 的数据，$n\le 10$

对于 $50\%$ 的数据，$n\le 500$

对于 $100\%$ 的数据，$n\le 2000$

$1\le h_i\le 10^6,1\le w_i\le L\le 10^9$