曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5978: Dairy Queen

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：25 Solved：20
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

奶牛Bassie去DQ打工，遇到一个客人给了一张好大面值的钞票，于是Bassie不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有n种硬币，对这些不同种的硬币进行编号，编号为i的硬币面值为a[i] 。因为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为total)(1≤total≤1000,1≤n≤1000,1≤a[i]≤300)
求一共有多少种解决方案？

Input

第一行为硬币总值total和硬币种类数n。
以下n行为数值a[i]，i=1,2,3...n

Output

一行，解决方案数

Sample Input Copy 

83 5
50
25
10
5
1

Sample Output Copy 

159

HINT

NPUT DETAILS:

Eight-three cents; standard American coins with values 50, 25, 10, 5, and 1

OUTPUT DETAILS:

Here are 2 of the 159 ways of making 83 cents:

0 x 50 0 x 25 0 x 10 0 x 5 83 x 1

0 x 50 0 x 25 0 x 10 1 x 5 78 x 1