样例下载

题目描述

有 N 件商品，编号为 1 ~ N。编号为 i 的商品的重量为 $W_i$，价格为 $P_i$。

现在要把这些商品进行捆绑销售。具体地，把这些商品分成若干份，每份装入到一个打包袋里，称为一包，该包的销售价等于该包商品中价格最高的那件商品的价格。由于打包袋承重有限，每包商品的总重量不能超过 M。另外，在进行打包的时候，要求打成一包的商品编号必须连续。当然，一包只包含一件商品也是有可能的。

恰好打包员是你的朋友，而你想把 N 件商品全部买下来。自然地，你希望花尽可能少的钱。所以你决定找到一种打包方案告诉你的朋友，从而使得你可以花最少的钱买下所有商品。

问：你最少需要花多少钱可以买下所有商品？

输入格式

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

接下来 $N$ 行,每行包含两个整数 $P_i$ 和 $W_i$。

输出格式

一个整数，表示买下所有商品需要花的最少钱数。

输入样例

4 10
5 7
9 2
8 5
13 2

输出样例

18

数据范围

$1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^9, 1 ≤ P_i ≤ 10^6, 1 ≤ W_i ≤ M$.