题目描述

给定一个容量为 C 的背包， n 个体积分别为 $w_1$​ , $w_2$ ​, ... , $w_n$ ​的物品，物品 i 放入背包能产生 $p_i$ ​的价值 ( i = 1 , 2 , ... , n , $p_i$ > 0 , $w_1$​ > 0)。

每个物品要么整个放入背包，要么不放。放入物品的总体积不能超过背包的总容量 C 。

要求找出最大价值的装包方案。

输入格式

第一行包含两个正整数 n 和 C ( 1 ≤ n ≤ 100 ，1 <= C <= 30000 )

第二行含 n 个正整数 $w_i$ 分别表示 n 个物品的体积 ( 1 <= $w_i$ <= C )。

第三行含 n 个正整数 $p_i$ 分别表示 n 个物品放入背包能产生的价值( 1 <= $p_i$ <= 1000 )。

输出格式

一个整数，代表最大价值。

样例

4 9
2 3 4 5
3 4 5 7

12