Extra
Time
7.5背包问题 Time:1s Memory:50M AC:15% Submit:7

题目描述

设有一个背包,可以放入的重量为m。现有n件物品,每个物品有个体积w和价值v。要求从n件物品中挑选若干件,使得放入背包的物品的体积之和<=m,且价值之和最大。

输入描述

第一行输入n,m。

接下来n行每行两个数分别表示每个物品的体积和重量。

输出描述

输出在不超过背包体积的情况下选中物品的最大价值和。

样例输入

3 6

1 2

2 4

5 5

样例输出

7

数据范围及提示

n<=20 m<=200