题目描述

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

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

每种硬币的数量都是无限的。

输入格式

输入包括 $3$ 行数据。

第一行：一个整数 $n$ 。

第二行：$n$ 个整数，表示长度为 $n$ 的整数数组 $\text{coins}$。

第三行：一个整数 $amount$。

输出格式

一行一个整数，表示可以凑成总金额所需的最少的硬币个数;或者 $-1$ ，表示没有任何一种硬币组合能组成总金额。

3 
1 2 5 
11

3

1
2
3

-1

1
1
0

0

3
1 5 11
15

3

说明/提示

数据范围与约定

$1 \leq n \leq 10^3$

$1 \leq \text{coins}_i \leq 10^9$

$0 \leq amount \leq 10^4$

样例解释

样例一：$11 = 5 + 5 + 1 = 2 \times 5 + 1$