题目描述

农夫 John 想到镇上买些补给。为了高效地完成任务，他想使硬币的转手次数最少。即使他交付的硬币数与找零得到的的硬币数最少。John 想要买 $t$ 样东西。有 $n$ 种货币参与流通，面值分别为 $v_1,v_2\dots v_n$。John 有 $c_i$ 个面值为 $v_i$ 的硬币。我们假设店主有无限多的硬币，并总按最优方案找零。

输入格式

• Line $1$：两个整数 $n$ 与 $t$ 。
• Line $2$：$n$ 个数，表示 $v_1, v_2,\dots v_n$。
• Line $3$：$n$ 个数，表示 $c_1, c_2,\dots c_n$。

输出格式

• Line $1$：一个整数，表示最优方案的转手次数，如无解输出 -1 。

3 70
5 25 50
5 2 1

3

数据规模与约定

对于 $100\%$ 的数据，$1\le t\le 10^4$，$1\le n\le 100$，$1\le v_i\le 120$，$0\le c_i\le 10^4$。

题目来源

Gold