题目描述

现有 $N$ 种硬币，编号从 $1$ 到 $N$，每种硬币的数量无限。已知第 $i$ 种硬币的重量为 $w_i$，面额为 $v_i$。 请你选取若干枚硬币，要求选取的所有硬币的总重量不超过 $C$，求能获得的最大总面额。

输入格式

第一行：一个正整数 $N$，表示硬币的种类数。

第二行：一个正整数 $C$，表示允许的最大总重量。

第三行：$N$ 个用空格分隔的正整数，依次表示第 $1$ 到第 $N$ 种硬币的重量。

第四行：$N$ 个用空格分隔的正整数，依次表示第 $1$ 到第 $N$ 种硬币的面额。

输出格式

输出一行一个整数，表示在总重量不超过 $C$ 的限制下，能获得的最大总面额。

样例输入

3
5
1 2 5
1 3 6

样例输出

7

样例解释

总重量上限为 5，最优选取方案为： 选取 2 枚重量为 2、面额为 3 的硬币，加上 1 枚重量为 1、面额为 1 的硬币。 总重量为 $2×2 + 1 = 5$，符合重量限制；总面额为 $3×2 + 1 = 7$，为所有合法方案中的最大值。

数据范围

• $1 \le N \le 100$
• $1 \le C \le 1000$
• 对于所有硬币，$1 \le \text{重量} \le 100$，$1 \le \text{面额} \le 100$