0-1背包问题

题目描述

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

输入

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

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

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

其中：1 ≤ N ≤ 100，1 ≤ C ≤ 10^5 ，1 ≤ w_i ≤ 1000，1 ≤ v_i ≤ 1000。

输出

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

样例

来源

动规专题