The Fewest Coins G

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

农夫 John 想到镇上买些补给。为了高效地完成任务，他希望付款硬币数与找零硬币数之和尽量少。

John 想购买价值为 $T$ 的物品。有 $N$ 种流通硬币，面值分别为 $V_1,V_2,\dots,V_N$。John 有 $C_i$ 枚面值为 $V_i$ 的硬币。店主拥有每种硬币的数量均视为无限，并且总会采用最优的找零方案。

请输出一次交易中转手硬币总数的最小值；如果无法完成交易，输出 -1。

输入格式

第一行包含两个整数 $N,T$。

第二行包含 $N$ 个整数 $V_1,V_2,\dots,V_N$。

第三行包含 $N$ 个整数 $C_1,C_2,\dots,C_N$。

输出格式

输出一个整数，表示答案；无解时输出 -1。

样例输入 1

3 70
5 25 50
5 2 1

样例输出 1

3

样例解释

John 支付一枚面值 $50$ 的硬币和一枚面值 $25$ 的硬币，店主找回一枚面值 $5$ 的硬币，共转手三枚硬币。

数据范围

对于所有数据：

• $1\le N\le100$；
• $1\le T\le10000$；
• $1\le V_i\le120$；
• $0\le C_i\le10000$；
• 不同种硬币的面值可能相同。

子任务