3079 - 最大价值背包

有n种物品,第i种物品的重量和价格为wi、vi。每种物品数量无限。背包最大载重量为C。问如何放置物品,可使背包内物品价值之和最大。注意,背包不一定装满。

输入

第一行两个正整数n和C。 第二行为n个正整数wi, i=1,2,...,n。 第三行为n个正整数vi, i=1,2,...,n。

输出

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

样例

输入

4 11
2 3 5 7
1 5 2 4

输出

9

提示

对于100%的数据,1\le n\le 100000, 1\le C\le 100000, 1\le w_i\le 10000,1\le v_i\le 10000

来源

动规专题

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