3011 - 0-1背包问题-2

有N件物品和一个容量为C的背包。放入第i件物品耗费的空间是w_i,得到的价值是v_i。求解在不超过容量的前提下,将哪些物品装入背包可使价值总和最大。

输入

第1行两个正整数,分别表示N和C,中间用一个空格隔开。

第2行N个正整数,表示w_i,中间用一个空格隔开。

第3行N个正整数,表示v_i,中间用一个空格隔开。

其中:1≤N≤1000,1≤C≤10^6 ,1≤w_i≤10000,1≤v_i≤10000。

输出

一行一个正整数,表示最大的价值总和。

样例

输入

4 20
8 9 5 2
5 6 7 3

输出

16

提示

本题与0-1背包(2010)题面完全一致,唯一的区别为N的取值范围和内存约束。

来源

动规专题

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