文理学院程序设计在线练习


0-1背包问题

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 1422   Accepted Submission(s): 546
Problem Description

给定n种物品和1个背包,物品i的重量是wi,其价值为vi,背包的容量为C。要求选择装入背包的物品,使得装入背包中物品的总价值最大。

Input

每组测试数据包含3行,第1行为n和c,表示有n(0<=n<=400)个物品且背包容量为c (c<=1500),第二行为这n个物品的重量wi(1<=wi<=1000),第三行为这n个物品的价值vi。背包容量和物品重量都为整数。

Output

输出装入背包的最大总价值,每个答案一行。

Sample Input
5 10
2 2 6 5 4
6 3 5 4 6
5 10
3 1 5 9 3
6 6 2 13 2
Sample Output
15
19