Rich Person's Coin Exchange

A person has an enormous amount of money. They want to exchange the entire amount into coins and store it.

The more coins there are, the harder they are to store, so they want to use the given coin denominations to make exactly the same amount with as few coins as possible. The amount must not decrease or increase by even 1 won.

Find the minimum number of coins needed to make exactly M won.

The first line contains the amount M. (10^9 <= M <= 10^18)

The second line contains the number of coin denominations N. (1 <= N <= 1,000)

The third line contains N coin values A_i. (1 <= A_i <= 10,000)

A 1-won coin is always included among the denominations, so every amount can be made.

Print the minimum number of coins needed to make exactly M won.