问题描述

有 $N$ 件物品和一个体积为 $M$ 的背包。第 $i$ 个物品的体积为 $v_i$，价值为 $w_i$。每件物品可以使用无限次。

请问可以通过什么样的方式选择物品，使得物品总体积不超过 $M$ 的情况下总价值最大，输出这个最大价值即可。

输入格式

第一行输入两个正整数 $N,M$。$(1\le N,M\le 1000)$

接下来 $N$ 行，每行输入两个整数 $v_i,w_i$。$(0\le v_i,w_i\le 1000)$

输出格式

输出一个整数，表示符合题目要求的最大价值。

样例输入

4 5
1 2
2 4
3 4
4 5

样例输出

10

说明

你可以选择 $1$ 个第一个物品和 $2$ 个第二个物品。