题目描述

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

John 想要买价值为 $T$ 的东西。有 $N$（$1 \le N \le 100$）种货币参与流通，面值分别为 $V_1,V_2,\dots,V_N$（$1 \le V_i \le 120$）。John 有 $C_i$ 个面值为 $V_i$ 的硬币（$0 \le C_i \le 10 ^ 4$）。

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

输入格式

第1行：两个空格分隔的整数：N和T。 第2行：N个空格分隔的整数，分别为V1、V2、。。。，VN硬币（V1，…VN） 第3行：N个空格分隔的整数，分别为C1，C2。。。，CN

输出格式

第1行：包含单个整数的行，即付款和找零所涉及的最小硬币数。如果农民约翰不可能支付和收到确切的零钱，输出-1。

3 70
5 25 50
5 2 1

3

提示

农民约翰用一枚50美分和一枚25美分的硬币支付75美分，并收到一枚5美分的硬币作为零钱，总共在交易中使用了3枚硬币。