题目描述

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

输入格式

一共输入4行数据

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

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

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

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

输出格式

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

样例

输入样例

3 10
5 4 3
10 5 4
1 2 3

输出样例

8

数据范围与提示

$1 \leq n \leq 20$

$50 \leq w \leq 100$

$1 \leq v_i,c_i,p_i \leq 10^7$

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