题目描述

$\red{Farmer John }$闲来无事的时候总喜欢坐下来看书。这些年来，他一共收集了 $\red{N }$本书$\red{（1≤}$$\red{N≤}$$\red{2000）}$，他打算搭一共新的书架来装这些书。

每本书都有个宽度 $\red{w_i}$和高度 $\red{h_i，}$书必须按顺序来摆放（即同一层书架摆的书必须是连续的一个区间）。每层书架的总宽度不能超过 $\red{L（}$$\red{1 \leq L \leq 10^9 ）}$，每层书架的高度等于这一层最高的书的高度，整个书架的高度等于每层书架的高度之和。

现在请你帮 $\red{FJ }$求出书架高度的最小值。

输入格式

第一行两个整数 $\red{N,L}$。

接下来 $\red{N }$行，每行两个整数 $\red{h_i,w_i（}$$\red{1 \leq h_i \leq 10^6，}$$\red{1 \leq w_i \leq L）}$。

输出格式

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

样例

输入样例

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

输出样例

21

提示

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