题目描述

有 $N$ 个美丽的手镯，每个手镯有一个重量与美丽值，现在只能拿走最重总和不超过 $M$ 的手镯，求最大的美丽值之和。

输入格式

第一行输入两个整数 $N,M$ 。

第二行到第 $N+1$ 行每行输入两个整数 $W_i,D_i$ ，表示重量与美丽值。

输出格式

一个整数表示最大的美丽值。

输入输出样例

4 6
1 4
2 6
3 12
2 7

23

约定

$1 \le N \le 3402，1 \le M \le 12880，1 \le W_i \le 400，1 \le D_i \le 100$ 。

来源

信友队题库，题目ID：3355