#S5082. 实现01背包

实现01背包

给定 N 件物品和一个容积为 V 的背包。已知第 i 件物品的体积是 cic_i

,价值是 wiw_i。一个物品要么装要么不装,问应该如何选择装入背包的物品,使得装入背包的物品的总价值为最大。

输入格式

输入的第一行,两个整数N、V,表示 有 N 件物品 (1N100,1V10000)(1 \leq N \leq 100,1 \leq V \leq 10000) 。 接下来N行,每行两个整数wiw_icic_i,1表示第 i 件物品的体积是 cic_i,价值是 wiw_i

输出格式

输出包括一行,仅一个整数, 为背包中最多可以放入的物品总价值。

样例输入

5 10
2 1
3 5
2 5
3 4
4 3

样例输出

9