题目描述

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

小珅想要买价值为 T（1≤T≤10000）的东西。有 N（1≤n≤100）种货币参与流通，面值分别为 $V_{1}$，$V_{2}$，…，$V_{n}$（1≤$V_{i}$≤120）。小珅有 $C_{i}$ 个面值为 $V_{i}$ 的硬币（0≤$C_{i}$≤10000）。

我们假设店主有无限多的硬币，并总按最优方案找零。注意无解输出 −1。

输入格式

第 1 行，2 个整数 N，T。

第 2 行，n 个整数 $V_{1}$，$V_{2}$，…，$V_{n}$。

第 3 行，n 个整数 $C_{1}$，$C_{2}$，…，$C_{n}$。

输出格式

输出付钱和找零总共需要用到的最少的硬币数。无解输出 −1。

3 70
5 25 50
5 2 1

3

10 3949
37 40 42 44 51 59 68 72 90 92
862 552 858 751 109 291 111 87 394 369

44

1 6
3
2

2

数据范围与约定

1≤T≤10000，1≤n≤100，1≤$V_{i}$≤120，0≤$C_{i}$≤10000