题面翻译

你有 $N$ 个物品和容量为 $W$ 的背包，每个物品要么选要么不选,它们的体积为 $w_i$，价值为 $v_i$，求总体积至多为 $W$ 情况下能拿走物品价值的最大值。

【数据范围】

$1\le N \le 100$，$1\le W \le 10^9$，$1 \le w_i \le 10^9$

$w_1 \le w_i \le w_1+3 (i=2,3,\cdots N)$

$1 \le v_i \le 10^7$

$W,w_i,v_i$ 都是整数

输入格式

$N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ : $w_N$ $v_N$

输出格式

输出答案

样例 #1

样例输入 #1

4 6
2 1
3 4
4 10
3 4

样例输出 #1

11

样例 #2

样例输入 #2

4 6
2 1
3 7
4 10
3 6

样例输出 #2

13

样例 #3

样例输入 #3

4 10
1 100
1 100
1 100
1 100

样例输出 #3

400

样例 #4

样例输入 #4

4 1
10 100
10 100
10 100
10 100

样例输出 #4

0

提示

Sample Explanation 1

$1,\ 3$ 個目の物を選ぶと良いです。

Sample Explanation 2

$2,\ 4$ 個目の物を選ぶと良いです。

Sample Explanation 3

すべての物が選べます。

Sample Explanation 4

$1$ 個も物が選べません。