题目描述

有 $n$ 件艺术品，必须按照编号从小到大的顺序摆放在若干层展架上。艺术品 $i$ 的高度为 $H_i$，宽度为 $W_i$。

每层展架只能放置编号连续的一段艺术品，并且这一层艺术品的宽度总和不能超过 $L$。这一层所需的高度等于其中最高艺术品的高度。整个展架的总高度等于所有层高度之和。

请计算摆放全部艺术品所需的最小总高度。

输入格式

第一行包含两个整数 $n,L$，分别表示艺术品数量和每层展架的宽度上限。

接下来 $n$ 行，每行包含两个整数 $H_i,W_i$，分别表示艺术品 $i$ 的高度和宽度。

输出格式

输出一个整数，表示展架的最小总高度。

样例

5 15
5 5
8 2
9 4
15 3
5 8

20

样例解释

将前 $4$ 件艺术品放在第一层，宽度总和为 $14$，该层高度为 $15$；第 $5$ 件艺术品单独放在第二层，高度为 $5$。总高度为 $20$。

数据范围与提示

• 对于 $16\%$ 的数据，$1 \le n \le 1000$
• 对于 $24\%$ 的数据，$1 \le n \le 5\times10^4$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$
• $1 \le L \le 10^9$
• $1 \le H_i \le 10^6$
• $1 \le W_i \le L$