题目描述

$Bob$ 到物流中心实习，“快递装箱问题”始终困扰着公司，问题基本描述如下：

• $n$ 件货物，第 $i$ 件货物重量是 $w_i$ , 高度是 $h_i$；
• 快递箱子能够承受的最大重量是 $W$, 一个快递箱的成本等于装入货物的最大高度；
• 要将 $n$ 件货物分成连续的若干段，每段连续货物装入一个快递箱，当然这段货物不能超过箱子最大承受重量 $W$ ；

所有箱子的成本之和就是公司总支出项，公司希望通过编程求出总成本的最小值，以期望降低支出，获得收益。

$Bob$ 大学期间没有好好学习算法，显然他解决不了这个问题，他又想获得公司认可，于是求助于你。

输入格式

第一行两个整数 $n$ $W$

接下来 $n$ 行，每行两个整数 $h_i$ 和 $w_i$

输出格式

一个整数，表示总成本的最小值。

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

21

样例1解释

可以使用 $3$ 个箱子：$(1),(2,3,4),(5)$ , 那么 $3$ 个箱子代价是 $5+13+3=21$ , 没有其他更优方案。

10 82
20 3
18 6
16 9
14 12
12 15
10 18
8 21
6 24
4 27
2 30

30

下发数据：down.zip

数据规模与约定

所有数据满足： $1\le n \le 2 \times 10^5, 1 \le W \le 10^9, 1 \le w_i \le W , 1\le h_i \le 10^9$

$Subtask1$: $1\le n \le 100$ , $20$ 分

$Subtask2$: $1\le n \le 2\times 10^3$ , $30$ 分

$Subtask3$: 无其他限制 , $50$ 分