D. 零钱兑换

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给你一个整数数组 c ,表示不同面额的硬币;以及一个整数 m 表示总金额。

你可以认为每种硬币的数量是无限的。请计算并返回可以凑成总金额所需的 最少的硬币个数 。

如果没有任何一种硬币组合能组成总金额,返回 -1 。

输入格式

第一行,n

第二行,数组 c 的 n 个硬笔面额

第三行,m

输出格式

最少的硬币个数

样例

示例 1:

输入:

3
1 2 5
11

输出:

3 

解释:11 = 5 + 5 + 1

示例 2:

输入:

1
2
3

输出:

-1

示例 3:

输入:

1
1
0

输出:

0

数据范围与提示

1 <= n <= 12

1 <= c[i] <= 2^{31} - 1

0 <= m <= 10^4