#333. 零钱兑换(完全背包)

零钱兑换(完全背包)

零钱兑换(完全背包)

题目描述

给定一个整数金额 amountamount 和若干种不同面值的硬币 coinscoins,每种硬币的数量都是无限的。请计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额,返回 1-1

输入

第一行一个整数 amountamount,表示要凑成的目标金额(0amount100000 \le amount \le 10000)。 第二行若干个整数 coinscoins,表示可用的硬币面值(以空格分隔,读到行末结束)。

输出

一个整数,表示凑成目标金额所需的最少硬币个数;若无法凑成,输出 1-1

样例输入

5
1 2 5

样例输出

1