Harddp
Minimum Number of Coins
Time limit 2 s · Memory 64 MBAcceptance: —Solved by: 0
Statement
The first line contains the number of coin types n, the second line contains n distinct denominations, the third line contains the amount S. Print the minimum number of coins needed to make S; every denomination is available in unlimited quantity. If the amount cannot be made, print -1. For S = 0 the answer is 0.
Examples
Example 1
Input
3 1 2 5 11
Output
3
Example 2
Input
1 2 3
Output
-1
Constraints
- 1 ≤ n ≤ 50
- 1 ≤ denomination ≤ 10^4
- 0 ≤ S ≤ 10^4