Woburn Challenge 2017-18 Round 1 - Senior Division

Your friend is just getting into competitive programming, and is trying to solve the classic "change" problem. You'll give him a target value ~K~ ~(1 \le K \le 10^9)~ and some distinct coin denominations (each of which is between ~1~ and ~K~, inclusive), and he'll try to determine whether or not a total of ~K~ can be produced using a set of (possibly duplicate) coins having only those denominations. The algorithm he's come up with to do so is greedy - starting from an empty set of coins, it repeatedly adds on the largest possible coin which won't cause the total to exceed ~K~, until it either reaches a total of ~K~, or is unable to add on any more coins and gives up.

You're not sure what coin denominations you'd like to give him, but there are ~N~ ~(0 \le N \le 2\,000)~ distinct denominations which you definitely don't want to include. The ~i^{th}~ of these is ~D_i~ ~(1 \le D_i \le K)~.

Your friend is convinced that his algorithm is so good that he'll be able to attain a total of ~K~ no matter what denominations he's given! This is quite the bold claim. You'd like to prove him wrong by choosing a (possibly empty) set of denominations such that his algorithm will fail to reach a total of ~K~ using them. Note that it doesn't matter whether or not a more correct algorithm would succeed, as long as your friend's greedy algorithm fails to achieve a total of ~K~.

Clearly, one option would be to simply give your friend ~0~ denominations to use. However, that's too easy - you'd like to prove as convincingly as possible that their algorithm is sub-par. As such, you'd like to determine the maximum number of distinct denominations which you can give your friend, such that their algorithm will still fail to reach a total of ~K~ using them.

Subtasks

In test cases worth ~6/37~ of the points, ~K \le 20~.
In test cases worth another ~20/37~ of the points, ~K \le 1\,000~.

Input Specification

The first line of input consists of two space-separated integers, ~K~ and ~N~.
~N~ lines follow, the ~i^{th}~ of which consists of a single integer, ~D_i~, for ~i = 1 \dots N~.

Output Specification

Output a single integer, the maximum number of distinct denominations which you can give your friend.

Sample Input 1

7 4
3 7 6 1

Sample Output 1

2

Sample Input 2

4 1
3

Sample Output 2

0

Sample Explanation 2

In the first case, one possibility is to give your friend the set of denominations ~\{2, 4\}~. His algorithm would use a ~4~ coin followed by a ~2~ coin, and then give up.

In the second case, you must resort to giving your friend no denominations, as his algorithm would achieve a total of ~4~ if given any non-empty subset of the denominations ~\{1, 2, 4\}~.