3012 - 完全背包

有n种物品,第i种物品的重量和价格为wi、vi。每种物品数量无限。背包最大载重量为C。今要把背包装满,并使得背包内物品价值之和最大。

输入

第一行两个正整数n和C。

第二行为n个正整数wi, i=1,2,...,n。

第三行为n个正整数vi, i=1,2,...,n。

输出

背包所能容纳物品的最大价值。

样例

输入

4 10
2 3 4 7
1 3 5 9

输出

12

提示

对于100%的数据,有1≤N≤1000,1≤C≤10^6,1≤wi≤10000,1≤vi≤10000。

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题