Coin Change: Minimum Coins

Selby Transit is fitting its ticket machines with a coin hopper. When a passenger is owed change, the machine must hand it over in as few coins as possible — every extra coin is another thing to jam, count and refill. The hopper never runs dry, so each denomination stocked is available in any quantity. Some amounts cannot be made at all from the coins a machine stocks, and it has to say so rather than hand over the wrong money.

Task: Print the smallest number of coins that adds up to exactly the amount owed.

Input

Two lines. The first holds the amount owed, an integer from 0 to 10000. The second holds between 1 and 100 distinct positive integers separated by single spaces — the denominations stocked, in no particular order.

Output

One line holding a single integer: the fewest coins adding up to exactly the amount. A denomination may be used as many times as you like. Print -1 if the amount cannot be made exactly. An amount of 0 needs no coins, so print 0.

Example:

Input:
11
1 2 5

Output:
3

(11 = 5 + 5 + 1)