J. 一般性的最少硬币组成问题

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

从n种币值为a[1..n]的硬币中,任选几个硬币组成价值为V的一堆货币,问最少需要几个硬币?其中每种硬币的数量没有限制。1<=n<=100,1<=v<=100000,1<=a[i]<=100000

输入中有两行:第一行有两个数v和n;第二行有n个以空格分隔的数,表示n个币值.

输出只有一行,该行只有一个数,表示所需的最少硬币数, 如果无论如何选取硬币,均不能得到币值v,则输出0.

10 2 
3 5