J17 实践-6 喵喵的烦恼

题目描述

在猫猫国家，喵喵是一位非常著名的数学家。她沉浸在计算中，每次购物都想用最少的硬币。（购物的数字包括她给商店的硬币和商店给她的支持。）

现在，喵喵想买 $T$ 猫币的用品，猫猫王国的货币系统有 $N$ 种不同的硬币，值为 $V_1,V_2,\ldots,V_N$，喵喵带着价值 $V_1$ 的 $C_1$ 枚硬币、价值 $V_2$ 的 $C_2$ 枚硬币……和价值 $V_N$ 的 $C_N$ 枚硬币。 店主有无限量的硬币供应，并且总是以最有效的方式找零。但是喵喵是一个低调的女孩，她不喜欢一次支付超过20000元。

输入格式

第一行：两个空格分隔的整数：$N$ 和 $T$；

第二行：$N$ 个空格分隔的整数，分别为$V_1,V_2,\ldots,V_N$；

第三行：$N$ 个空格分隔的整数，分别为$C_1,C_2,\ldots,C_N$

输出格式

一个整数，表示硬币的最小数量。如果无法支付和接收准确的零钱，则输出-1。

样例输入

3 70
5 25 50
5 2 1

样例输出

3

数据范围

对于 $100\%$ 数据：$1\le T \le 10000$，$1 \le N \le 100$ ，$1 \le V_i \le 120$ , $0 \le C_i \le 10,000$。