Coin Change

Problem statement

A ticket machine returns change using an unlimited supply of several coin denominations. It needs the fewest coins that exactly match a requested amount; returning a larger amount or a remainder is not permitted. Your task Find the minimum number of coins needed to make amount, or -1 if no exact combination exists. Each denomination may be used any number of times. Important details Greedily taking the largest coin is not always optimal. An amount of zero needs zero coins. Denominations are positive, so a dynamic program can build answers for increasing amounts without cyclic dependencies. Worked example With denominations [1, 3, 4] and amount 6, two coins of value 3 are optimal. Choosing 4 first would require two additional 1 coins, so the answer is 2.

Input format

First line: n amount. Next line: n coin denominations.

Output format

Print the minimum coin count or -1.

Constraints

1 <= n <= 12; 0 <= amount <= 10000; 1 <= denominations <= 2147483647.

Sample input

3 6
1 3 4

Sample output

2