题目描述

艺术家艾丽莎热爱艺术品，她决定在家中打造一个新的艺术展架来展示她收藏的所有艺术作品。

她收集了 $N$ 件艺术品（编号 $1 \sim N$），第 $i$ 件艺术品的宽度为 $W_i$，高度为 $H_i$。艺术品需要按照收藏的顺序摆放在艺术展架上。

假设第一层架子展示编号 $1$ 到 $k$ 的艺术品，那么第二层架子应该从编号为 $k + 1$ 件艺术品开始展示，依此类推。每层架子的总宽度最大为 $MaxW$。

每层架子最低高度为：该层上最高的艺术品的高度，整个艺术品展架的高度是所有层的高度的总和（不考虑架子上木板的厚度）。

请帮助艺术家艾丽莎计算整个艺术展架的最小可能高度。

输入格式

第一行读入两个数 $N$ 和 $MaxW$。

接下来 $N$ 行，每行读入两个数 $H_i$ 和 $W_i$。

输出格式

输出一个整数，代表艺术展架高度的最小值。

样例

输入

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

输出

20

输入

10 300
5675 94
2355 33
6000 63
6977 63
1730 68
3431 92
5827 32
1724 54
280 28
8504 9

输出

15481

样例解释

样例 $1$ 解释：

以下是一个高度最小的可行方案：

将编号为 $1 \sim 4$ 的艺术品放到第 $1$ 层，第 $1$ 层的高度为第 $4$ 个艺术品的高度 $15$，第 $1$ 层艺术品总宽度为 $5 + 2 + 4 + 3 = 14$ 没有超过每层的限宽。

将编号为 $5$ 的艺术品放到第 $2$ 层，第 $2$ 层的高度为 $5$，因此总高度为 $20$。

数据范围

对于 $16\%$ 的数据满足：$1 \le N \le 1000$。

对于 $24\%$ 的数据满足：$1 \le N \le 50000$。

对于 $100\%$ 的数据，满足：$1 \le N \le 10^5$，$1 \le MaxW \le 10^9$，$1 \le H_i \le 10^6$，$1 \le W_i \le MaxW$。