题目描述

你有$N$个物品和一个重量为$W$的背包。第$i$个物品的重量为$w_i$，价值为$v_i$。

你需要选择一些物品放入背包中，其中被选中物品的总重量不能超过$W$。

你的目标是使被选中物品的总价值最大化。

约束条件

• $1 \leq N \leq 100$
• $1 \leq W \leq 10^9$
• $1 \leq w_i \leq 10^9$
• 对于所有的$i = 2,3,...,N$，有$w_1 \leq w_i \leq w_1 + 3$。
• $1 \leq v_i \leq 10^7$
• $W$、每个$w_i$和$v_i$都是整数。

---

输入

输入以以下格式从标准输入给出：

$N\ W$

$w_1\ v_1$

$w_2\ v_2$

:

$w_N\ v_N$

输出

输出被选中物品的最大可能总价值。

---

示例输入1

4 6
2 1
3 4
4 10
3 4

示例输出1

11

应该选择第一个和第三个物品。

---

示例输入2

4 6
2 1
3 7
4 10
3 6

示例输出2

13

应该选择第二个和第四个物品。

---

示例输入3

4 10
1 100
1 100
1 100
1 100

示例输出3

400

可以把所有物品都拿起来。

---

示例输入4

4 1
10 100
10 100
10 100
10 100

示例输出4

0

什么都不拿。