[Usaco2006 Dec]The Fewest Coins 找零钱

农夫 John 想到镇上买些补给。为了高效地完成任务，他想使硬币的转手次数最少，即使他交付的硬币数与找零得到的硬币数之和最少。

John 想要买价值为 $T$ 的东西。有 $N$ 种货币参与流通，面值分别为 $V_1, V_2, \ldots, V_N$。John 有 $C_i$ 个面值为 $V_i$ 的硬币。

我们假设店主有无限多的硬币，并总按最优方案找零（即找零所用的硬币数最少）。

输入格式

第 $1$ 行：两个整数 $N$ 与 $T$。

第 $2$ 行：$N$ 个数，表示 $V_1, V_2, \ldots, V_N$。

第 $3$ 行：$N$ 个数，表示 $C_1, C_2, \ldots, C_N$。

输出格式

一个整数，表示最优方案的转手次数；如无解输出 $-1$。

样例输入

3 70
5 25 50
5 2 1

样例输出

3

数据范围

• $1\le T\le 10^4$；
• $1\le N\le 100$；
• $1\le V_i\le 120$；
• $0\le C_i\le 10^4$。

来源与许可

本题为 USACO 2006 Dec 试题「The Fewest Coins 找零钱」，题面与测试数据整理自 BZOJ 1716。

样例 1

输入

3 70
5 25 50
5 2 1

输出

3