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


二维费用背包问题

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

Total Submission(s): 110   Accepted Submission(s): 56
Problem Description

给定N种物品和1个背包,物品i的体积是ai,重量是bi, 价值为vi,背包的体积为V,背包的最大承载重量W。要求选择装入背包的物品,使得装入背包中物品的总价值最大。

Input

每组测试数据包含4行,第1行为N,V,W,表示有N个物品且背包体积为V和载重量W,第2行为这N个物品的体积ai,第3行为这N个物品的重量bi,第4行为这N个物品的价值vi。所有输入数字都为整数,范围大于0,小于等于100。处理到文件结束。

Output

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

Sample Input
4 3 1
1 1 1 2
2 2 1 1
3 3 1 3
Sample Output
3