偷东西(01背包)

题目描述

一个小偷拿着一个容量有限（容量设为w）的背包去商店偷东西，每个商品都有自己的体积v和价值c，并且每个商品只有一件。小偷的目的就是用这个容量有限的背包装满价值总量最大的东西。 现在给出n件商品的体积 $v_i$ (i从1到n) 和价值 $c_i$(i从1到n)以及背包的容量w，请求出在这n件商品中用一个容量为w的背包能够拿到的商品的最大价值是多少。

输入格式

一共输入3行数据

第一行输入2个正整数 n w（n表示商品数量，w表示背包容量）

第二行输入n个正整数 $c_i$(i从1到n，ci表示第i件商品的价值）

第三行输入n个正整数 $v_i$(i从1到n，vi表示第i件商品的体积)

输出格式

输出一个正整数，表示这n件商品中用一个容量为w的背包能够拿到的商品的最大价值。

样例 #1

样例输入 #1

5 10
1 2 3 4 5
5 4 3 2 1

样例输出 #1

14

样例 #2

样例输入 #2

5 15
5 3 9 4 6
3 7 5 2 8

样例输出 #2

19

提示

20>=n>=1

100>=w>=50

$v_i$、$c_i$以及最后的最大价值都是在in范围内