Problem K: 最少找零钱（动规课程A）（4.3）

Problem K: 最少找零钱（动规课程A）（4.3）

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 6Submit: 9Statistics

Description

      Google面试题：假设你是一家自动售货机制造商的程序员。你的公司正设法在每一笔交易 找零时都能提供最少数目的硬币以便工作能更加简单。已知硬币有m种。假设一个顾客投了1美元来购买n美分的物品 ，你用来找零的硬币的最小数量是多少？

Input

第一行2个整数n、m，范围[1..100]。

 第二行m个不同的整数，范围[1..100]。保证其中一定有一个1 。


Output

一个整数。

Sample Input Copy 

35 4
1 5 10 20

Sample Output Copy 

4
Submit