题目描述

仓库里有 $n$ 种货物，第 $i$ 种货物每件占用 $w_i$ 单位容量，价值为 $v_i$。每种货物都有无限多件。

现在有一个容量为 $W$ 的货箱。管理员需要选择一些货物，使它们占用的容量之和恰好等于 $W$，并希望装入货物的总价值尽可能大。

每种货物可以不选，也可以选任意多件。请你求出恰好装满货箱时的最大总价值。如果无论怎样选择都无法恰好装满，输出 $-1$。

输入格式

第一行两个整数 $n,W$，分别表示货物种类数和货箱容量。

接下来 $n$ 行，第 $i$ 行两个整数 $w_i,v_i$，分别表示第 $i$ 种货物每件占用的容量和价值。

输出格式

输出一行一个整数，表示恰好装满货箱时的最大总价值；如果无法恰好装满，输出 $-1$。

3 10
3 5
4 7
6 12

19

2 7
2 3
4 8

-1

1 6
2 9

27

样例解释

样例 1 中，选择第二种货物一件、第三种货物一件，占用容量 $4+6=10$，总价值为 $7+12=19$，是恰好装满的方案中的最大值。

样例 2 中，无论选择多少件货物，占用的总容量都是偶数，因此不能恰好装满容量为 $7$ 的货箱。

样例 3 中，选择三件货物可以恰好装满，总价值为 $3\times9=27$。

数据规模与约定

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

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