题目描述

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

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

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

输入格式

第一行包含两个正整数 $n$ 和 $C$ ( $1 \le n \le 1000$ ，$1 \le C \le 30000$ )

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

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

输出格式

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

样例

4 9
2 3 4 5
3 4 5 7

12