1984: 完全背包问题

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：51 Solved：19

Description

      有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装⼊背包的物品重量不超过背包容量 且价值最⼤ 。物品数量没有限制，可以选0个或者任意多个。 

      请注意: 这里每件物品不只有一个了。可以选0个或者选择任意多个。


样例数据见上图。选B物品一件及D物品三件，装入背包重量为7 ，价值为17最大。

Input

输入共有三行。第一行为 n( n件物品)及 m(背包容量为 m)。第二行为 n件物品的重量数据 w。第三行为 n件物品的价值数据 v 。

Output

输出一个数据为装入物品后背包的最大价值。

Sample Input Copy 

5 7
4 1 6 2 3
6 2 9 5 6

Sample Output Copy 

17

HINT

提示:
1=< n,m <=5000
1=<数组数据<=5000