{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e在现实生活中,我们经常遇到硬币找零的问题,例如,在发工资时,财务人员就需要计算最少的找零硬币数,以便他们能从银行拿回最少的硬币数,并保证能用这些硬币发工资。我们应该注意到,人民币的硬币系统是 $100$,$50$,$20$,$10$,$5$,$2$,$1$,$0.5$,$0.2$,$0.1$,$0.05$,$0.02$,$0.01$ 元,采用这些硬币,我们可以对任何一个工资数用贪心算法求出其最少硬币数。但不幸的是:我们可能没有这样一种好的硬币系统,因此用贪心算法不能求出最少的硬币数,甚至有些金钱总数还不能用这些硬币找零。例如,如果硬币系统是 $40$,$30$,$25$ 元,那么 $37$ 元就不能用这些硬币找零;$95$ 元的最少找零硬币数是 $3$。又如,硬币系统是 $10$,$7$,$5$,$1$ 元,那么 $12$ 元用贪心法得到的硬币数为 $3$,而最少硬币数是 $2$。 \u003c/p\u003e\u003cp\u003e你的任务就是:对于任意的硬币系统和一个金钱数,请你编程求出最少的找零硬币数。\u003c/p\u003e\u003ch3\u003e输入格式\u003c/h3\u003e\u003cp\u003e第一行,两个整数 $N$ 和 $M$,其中 $1\\le N \\le 50$ 为硬币系统中不同硬币数,$1\\le M\\le 100000$ 为需要用硬币找零的总数。 \u003c/p\u003e\u003cp\u003e第二行为 $N$ 个整数 $a_i\\ (1\\le a_i \\le 1000)$,它们是硬币系统中各硬币的面值。 \u003c/p\u003e\u003ch3\u003e输出格式\u003c/h3\u003e\u003cp\u003e请输出最少的找零硬币数,输入不存在输出 $-1$。\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 12\n10 7 5 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}