题目描述

有 $N$ 件模型，必须按照给定顺序放入一个多层展柜。第 $i$ 件模型的高度为 $h_i$，宽度为 $w_i$。

每一层只能放置原序列中连续的一段模型，这一层模型的宽度之和不能超过 $W$，这一层的高度等于其中最高模型的高度。展柜总高度等于所有层高度之和。

请计算展柜的最小总高度。

输入格式

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

接下来 $N$ 行，每行包含两个整数 $h_i,w_i$，分别表示一件模型的高度和宽度。

输出格式

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

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

23

数据范围与提示

• $1 \le N \le 2000$
• $1 \le W \le 10^9$
• $1 \le h_i \le 10^6$
• $1 \le w_i \le W$