题目描述

给你一个长度为n的整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

输入格式

输入包括3行数据。

第一行一个整数n 。

第二行为n个整数面额。

第三行一个整数amount。

输出格式

输出包括一行，最少硬币数或-1。

样例

3 
1 2 5 
11

3

提示

1 ≤ n ≤ 12

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

0 ≤ amount ≤ $10^4$