100 #663. 偷东西(多重背包)

偷东西(多重背包)

题目描述

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

输入格式

一共输入4行数据

第一行输入2个正整数 n w(n表示商品种数,w表示背包容量)

第二行输入n个正整数 cici(i从1到n,ci表示第i种商品的价值)

第三行输入n个正整数 vivi(i从1到n,vi表示第i种商品的体积)

第四行输入n个正整数 pipi(i从1到n,vi表示第i种商品的数量)

输出格式

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

样例

输入样例

3 10
5 4 3
10 5 4
1 2 3

输出样例

8

数据范围与提示

1n20 1 \leq n \leq 20

50w100 50 \leq w \leq 100

1vi,ci,pi107 1 \leq v_i,c_i,p_i \leq 10^7

最后的最大价值都是在int范围内