题目描述

当农夫约翰不挤牛奶、不堆干草、不把牛排好队、不筑篱笆的时候，他喜欢坐下来读一本好书。多年来，他已经收集了 $N$ 本书 ($1 \leq N \leq 2000$)，他想建一套新的书架来装这些书。每本书有宽度 $W(i)$ 和高度 $H(i)$。这些书需要按顺序添加到一组书架上；例如，第一个书架应该包括书 $1$ 到 $k$，第二个书架应该从 $k+1$ 开始，以此类推。每个书架的总宽度最多为 $L$ ($1 \leq L \leq 1000,000,000$)。书架的高度等于书架上最高的一本书的高度，整个书架的高度是所有单独书架高度的总和，因为它们都是垂直堆放的。

请帮助FJ计算整个书架可能的最小高度。

输入格式

• 第 $1$ 行：两个以空格分隔的整数：$N$ 和 $L$。
• 行 $2$ 到 $1 + N$：行 $i + 1$ 包含两个空格分隔的整数：$H(i)$ 和 $W(i)$（$1 \leq H(i) \leq 1,000,000$；$1 \leq W(i) \leq L$）。

输出格式

• 第 $1$ 行：书架组的最小可能总高度。

输入样例

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

输出样例

21