题目描述

当农夫约翰不在挤牛奶、堆干草、排列他的奶牛或建造围栏时，他喜欢坐下来读一本好书。多年来，他已经收集了 $N$ 本书（$1 \leq N \leq 100,000$），他想建一个新的书架来放置这些书。

每本书 $i$ 有一个宽度 $W(i)$ 和高度 $H(i)$。这些书需要按顺序放到一组书架上；例如，第一个书架应包含书 1 到 $k$，第二个书架应从书 $k+1$ 开始，依此类推。每个书架的总宽度最多为 $L$（$1 \leq L \leq 1,000,000,000$）。书架的高度等于该书架上最高的书的高度，而整个书架组的高度是所有单个书架高度的总和，因为它们都是垂直堆叠的。

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

输入格式

第一行：两个数 $N$ 和 $L$。

接下来 $N$ 行每行两个数 $H_i$ 和 $W_i$。$(1 \le H(i) \le 1,000,000;1 \le W(i) \le L)$.

输出格式

一个数，书架高度的最小值。

输入输出样例 #1

输入 #1

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

输出 #1

21

说明/提示

（由 ChatGPT 4o 翻译）