题目描述

工坊准备使用现有材料制作商品。一共有 $n$ 种商品，制作一件第 $i$ 种商品需要消耗 $w_i$ 单位材料，并能获得 $v_i$ 元收益。

每种商品都可以制作任意多件，也可以不制作。工坊一共有 $W$ 单位材料，制作所有商品消耗的材料总量不能超过 $W$，剩余材料可以不用。

请你计算工坊最多可以获得多少元收益。每件商品必须完整制作，不能只制作一部分。

输入格式

第一行两个整数 $n,W$，分别表示商品种类数和材料总量。

接下来 $n$ 行，每行两个整数 $w_i,v_i$，分别表示制作一件第 $i$ 种商品需要的材料数量和获得的收益。

输出格式

输出一行一个整数，表示最多可以获得的收益。

3 7
2 5
3 7
4 9

17

2 10
6 13
5 10

20

2 3
4 10
5 20

0

样例解释

样例 1 中，制作两件第 $1$ 种商品和一件第 $2$ 种商品，共消耗 $2+2+3=7$ 单位材料，获得 $5+5+7=17$ 元收益。

样例 2 中，制作两件第 $2$ 种商品，共消耗 $10$ 单位材料，获得 $20$ 元收益。

样例 3 中，材料不足以制作任何一件商品，因此最多获得 $0$ 元收益。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le100$，$1\le W\le2000$，$1\le w_i\le2000$，$1\le v_i\le10^9$。

答案可能超过 $32$ 位有符号整数的范围，请使用 $64$ 位整数类型保存答案。

• 子任务 1（30 分）：保证 $n\le12$，$W\le30$。
• 子任务 2（30 分）：保证 $n\le50$，$W\le500$。
• 子任务 3（40 分）：没有特殊限制。