Problem F: 0-1背包问题

Memory Limit：512 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：161 Solved：50

Description

    有 n件物品，每件物品的重量为 w[i]，其价值为 v[i]，现在有个容量为 m的背包，如何选择物品使得装入背包物品的价值最大。

    0-1背包问题指的是每个物品只能使用一次 

样例数据见上图。选A B及E三件物品，容量为8 ，价值为16最大。          

Input

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

Output

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

Sample Input Copy 

5 8
4 1 6 2 3
6 4 9 5 6

Sample Output Copy 

16

HINT

提示:

1=< n,m <=10000
1=<数组数据<=10000