Because Xin Yuan needed money to buy more hats in TF2, he decided to open a lemonade stand, and to do that, he needed money. Hence, he borrowed some from the most notorious loan shark in town. These sharks will come to his stand every day and ask for some money in the range of 1 to n. Because those loan sharks are not good at math, they can't count change very well and demanded exact amount to be paid. But Xin Yuan does not want to carry so many coins to his stand. Write a program to find the minimum number of coins he needs to carry.
The first line contains the values n and k.
The next line contains k numbers, the value of coins available. The value 1 is guaranteed to be inside.
Output the minimum number of coins he needs to carry.
1 ≤ n ≤ 4000, 1 ≤ k ≤ 1000.
Sample Input 1
1 2 3
Sample Output 1
He can carry 2 coins of value 1 and 2.
Sample Input 2
1 3 5
Sample Output 2
He can carry 2 coins of value 1, and 1 coin of value 3.