当前没有测试数据。

题目描述

小 $A$ 是知名高达模型收藏家，多年的收藏已经达到 $N$ 件之多。他急需一个精心设计的多层展柜，来防止熊孩子的破坏。

每件高达模型小 $A$ 已经按照年份以及版本做好了排序，也就是说放入展柜时必须按照原定的顺序摆放。

每件模型都会有一个高度和宽度。每层展架的宽度不会超过 $W$， 高度等于这层最高的高达的高度。整个展柜的高度等于每层高度之和。

已知每件高达的高度以及放入顺序，请你帮小 $A$ 计算一下展柜的最小高度是多少？

输入格式

第一行两个整数 $N, W$。

接下来 $N$ 行，每行两个整数分别表示每件高达的高度 $h_i$ 和宽度 $w_i$。

输出格式

输出一个整数。

样例

输入

5 10
4 7
9 2
8 5
14 2
5 8

输出

23

输入

6 5
1 1
1 1
1 1
1 1
100 1
100 1

输出

101

数据范围

对于 $10\%$ 的数据，满足 $1 \le N \le 5$。

对于 $20\%$ 的数据，满足 $1 \le N \le 10$。

对于 $100\%$ 的数据，满足 $1 \le N \le 2000$，$1 \le W \le 10^9$，$1 \le h_i \le 10^6$，$1 \le w_i \le W$。