问题说明

学贯中西后的Gold King，越发觉得抢商品，背包容量一定时抢最多的钱，那是so easy，只可惜现实生活中，没有抢的机会。一天，Gold King看到了大鹏的《大赢家》，觉得这个就是好的idea，于是开始了抢银行之旅。
Gold King背着容量为100的背包去银行抢钱。可是银行里存放着n(0<=n<=100)种面额的货币，每种货币的数量为m，每个对应货币的体积为v，该体积下价值为c都不同。求Gold King最多能偷走多少价值的东西，成为大赢家？要求使用二维数组。

输入格式

第一行输入一个整数n，表示n种货币，
第二行输入n种货币的体积v，
第三行输入n种货币的价值c，
第四行输入n种货币的数量m。

输出格式

输出对应Gold King能偷走的最多的价值。

样例1输入：
3
10 5 4
5 4 3
1 2 3
样例2输入：
8
79 25 56 2 34 65 66 73 
49 88 71 40 47 67 34 62 
1 3 5 6 8 1 4 4

样例1输出：
22
样例2输出：
504

提示

1<=v<=100
1<=c<=100
1<=m<=10

来源/分类

算法培训-14-多重/混合背包