该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

现在有 $N$ 种不同面值的硬币。第 $i$ 种硬币的面值为 $A_i$ 元，你手上有 $B_i$ 枚这种硬币。

现在你想购买一件价格为 $X$ 元 的商品。请问最少需要使用多少种不同面值的硬币才能凑出足够金额购买该商品？

如果无论如何都无法凑出足够金额，则输出 $-1$。 注意：

• 目标是最小化使用的硬币种类数，而不是最小化使用的硬币总数
• 允许支付超过 $X$ 的金额（不需要恰好支付 $X$）

输入格式

第一行两个整数 $N$ 和 $X$，表示硬币种类数和商品价格。

第二行$N$ 个整数 $A_1, A_2, ..., A_N$，表示各硬币面值。

第三行$N$ 个整数 $B_1, B_2, ..., B_N$，表示各硬币数量。

输出格式

输出一行一个整数，表示最少需要使用的硬币种类数，若无法购买则输出 $-1$。

输入输出样例

3 10
1 2 3
1 2 3

2

样例 $\tt \#1$说明

• 使用 $2$ 种硬币：$3$ 枚 $3$ 元硬币和 $1$ 枚 $2$ 元硬币，合计 $11$ 元（满足 $≥10$ 元）
• 无法仅用 $1$ 种硬币凑够金额，故答案为 $2$

3 10
1 2 3
1 2 1

-1

样例 $\tt \#2$说明

• 即使使用所有硬币 $(1×1 + 2×2 + 1×3 = 8)$ 也不够 $10$ 元，输出$-1$。

5 100
5 10 15 20 25
1 1 2 3 4

1

样例 $\tt \#3$说明

• 使用 $25$ 元硬币 $4$ 枚（$100$ 元）即可，故答案为$1$。

数据范围

测试点编号	$N$	$X$	$A_i, B_i$	特殊性质
$1∼4$	$\leq 10^3$	$\le 10^9$	$\leq 1000$	$A_i = 1$
$5∼8$				$B_i = 1$
$9∼12$				无
$13∼20$	$\leq 10^5$