#2096. Bookshelf

Bookshelf

题目描述

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

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

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

输入格式

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

接下来 N\red{N }行,每行两个整数 hi,wi\red{h_i,w_i(}1hi106\red{1 \leq h_i \leq 10^6,}1wiL\red{1 \leq w_i \leq L)}

输出格式

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

样例

输入样例

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

输出样例

21

提示

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