题目描述

农夫 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。

输入格式

Line 1: Two space-separated integers: N and T. Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN) Line 3: N space-separated integers, respectively C1, C2, ..., CN

输出格式

Line 1: A line containing a single integer, the minimum number of coins involved in a payment and change-making. If it is impossible for Farmer John to pay and receive exact change, output -1.

样例 #1

样例输入 #1

3 70
5 25 50
5 2 1

样例输出 #1

3

提示

农夫John支付50+25，店主找零5。