01 背包
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
01 背包
题目描述
有 件物品，第 件物品的重量为 ，价值为 。背包的容量为 ，每件物品最多选择一次。
要求选出的物品总重量恰好等于 ，求能获得的最大总价值。如果无法恰好装满背包，输出 -1。
输入格式
第一行两个整数 和 。
接下来 行，每行两个整数 和 。
输出格式
一行一个整数，表示恰好装满背包时的最大总价值；如果无法恰好装满，输出 -1。
样例
4 5
1 2
2 4
3 4
4 5
8
2 5
4 100
3 99
-1
数据范围
，，，。