恰好装满的藏宝箱

题目描述

探险者在遗迹深处发现一只容量为 $W$ 的古老宝箱，箱子只能恰好装满才能开启。有 $n$ 件物品，每件有体积和价值，只能取或不取且不可拆分。请你帮他在总占用体积恰好为 $W$ 的前提下，使宝物总价值最大；如果无法恰好装满，输出 $-1$。

输入格式

第一行包含两个整数 $n,W$。

接下来 $n$ 行，每行包含两个整数，表示一件物品的体积与价值。

输出格式

输出一个整数，表示恰好装满时可获得的最大总价值；若无法恰好装满，输出 $-1$。

输入输出样例 #1

输入 #1

4 7
3 5
2 4
4 6
5 7

输出 #1

11

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le W \le 2000$，体积与价值均在 $[1,10^4]$。EOF