题目描述

给你一个长度为 $n$ 的整数数组 $coins$ ，表示不同面额的硬币；以及一个整数 $amount$ ，表示总金额。

计算并输出可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，输出 -1 。

你可以认为每种硬币的数量是无限的。

输入格式

第一行输入一个整数 $n$ ，表示数组的长度。

第二行输入一个长度为 $n$ 的数组 $coins$ 。

第三行输入一个整数 $amount$ 。

输出格式

计算并输出可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，输出 -1 。

3
1 2 5
11

3

1
2
3

-1

数据范围

$1 \leq n \leq 12$

$1 \leq coins[i] \leq 2^{31}-1$

$0 \leq amount \leq 10^4$