题目描述

贝西去了商场的珠宝店，发现了一个吊坠手链。当然，她要在$N(1\le N \le 3402)$个可以选择的吊坠中选择最好的一些吊坠挂在手链上。每个在可选列表上的吊坠有一个重量值$W_i(1\le W_i \le 400)$，一个"需求"分数$D_i(1\le D_i \le 100)$。每个吊坠最多可以被使用一次。贝西只能戴得动一个重量不大于$M(1\le M \le 12880)$的吊坠手链。 给定重量限制作为约束，以及带有重量及需求分数的吊坠列表，推导出最大的可能的分数加和。

输入

第1行：两个由空格分开的整数：$N$与$M$

第2行到第$N+1$行：第$i+1$行用两个由空格分开的整数$W_i$与$D_i$来描述了第$i$个吊坠。

输出

一行：一个整数，是在给定重量限制前提下，可能达到的吊坠“需求分数”加和的最大值。

样例

4 6
1 4
2 6
3 12
2 7

23

提示

No

来源

一本通在线评测