题目描述

传说过年的时候，会有各种宝藏出现，而你恰巧得到了一张宝藏图。

根据宝藏图的提示，你找到了宝藏，但是宝藏太多了，为了拿到的宝藏尽可能的贵重，于是你开始斟酌你自己的策略。

一共有n种宝藏，每种宝藏重量为$w_i$，价值为$v_i$，且数量无限多。

你的背包只有$W$大小承重，但是物以稀为贵，当宝藏被装进背包的时候，后续该宝藏的价值都将减少1。

请求出你能留下来的最多价值。

输入格式

输入共计$n+1$行

第一行输入两个数字$n,W$，分别表示宝藏的数量和背包的总承重

后续n行，每行输入两个数字$w_i,v_i$，分别表示宝藏的重量和价值。

输出格式

输出一行，表示答案

样例

2 10
3 5
2 4

16

样例1解释：

在第一个样例中，可以装两件第一种宝物和两件第二种宝物，总价值为5+4+4+3=16。

限制

3s, 256mb

数据范围

对于30%的数据，$1\leq{n,W,w_i}\leq{300},1\leq{v_i}\leq{300}$

对于另外30%的数据，$1\leq{n,W,w_i}\leq{3000},1\leq{v_i}\leq{10^9}$且额外满足所有的$w_i$都不同

对于100%的数据，$1\leq{n,W,w_i}\leq{3000},1\leq{v_i}\leq{10^9}$