货品整理（goods）

题目描述

某仓库共有 (n) 件不同的货品，每件货品都有原始体积 $(w_i) 和价值 (v_i)$。

运输前，工作人员需要将所有货品按照原始体积从小到大排序，并从 1 开始重新编号。

如果两件货品的体积相同，则按照它们在输入中出现的先后顺序排列。

由于包装设备的特殊要求，重新编号为 (i) 的货品，需要额外占用 (i-1) 单位的包装空间。

因此，这件货品最终占用的空间为：

$w_i+i-1$

仓库有一个容量为 (V) 的运输箱。

每件货品最多只能选择一次。

请计算在总占用空间不超过 (V) 的条件下，能够获得的最大总价值。

输入格式

第一行输入两个整数 (n,V)，分别表示货品数量和运输箱容量。

接下来 (n) 行，每行包含两个整数 $(v_i)$。

输出格式

输出一个整数，表示最大总价值。

输入输出样例 #1

输入

4 10
4 8
2 3
3 6
5 9

输出

14

样例解释

排序并重新编号后：

选择编号为 2 和 3 的货品，最终占用空间为 (4+6=10)，总价值为 (6+8=14)。

数据范围

• $(1\le n\le100)$
• $(1\le V\le2000)$
• $(1\le w_i\le2000)$
• $(1\le v_i\le10000)$