邮票

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 stamps.in 输出文件 stamps.out

usaco/Stamps(译by Felicia Crazy)

描述


已知一个N枚邮票的面值集合(如,{1分,3分})和一个上限K ——表示信封上能够贴K张邮票。计算从1到M的最大连续可贴出的邮资。

例如,假设有1分和3分的邮票;你最多可以贴5张邮票。很容易贴出1到5分的邮资(用1分邮票贴就行了),接下来的邮资也不难:

  • 6 = 3 + 3
  • 7 = 3 + 3 + 1
  • 8 = 3 + 3 + 1 + 1
  • 9 = 3 + 3 + 3
  • 10 = 3 + 3 + 3 + 1
  • 11 = 3 + 3 + 3 + 1 + 1
  • 12 = 3 + 3 + 3 + 3
  • 13 = 3 + 3 + 3 + 3 + 1。

然而,使用5枚1分或者3分的邮票根本不可能贴出14分的邮资。因此,对于这两种邮票的集合和上限K=5,答案是M=13。

格式
PROGRAM NAME: stamps
INPUT FORMAT:(file stamps.in)
第1行: 两个整数,K和N。K(1 <= K <= 200)是可用的邮票总数。N(1 <= N <= 50)是邮票面值的数量。
第2行..文件末: N个整数,每行15个,列出所有的N个邮票的面值,面值不超过10000。
 
OUTPUT FORMAT:(file stamps.out)

单独的一行,一个整数,从 1 分开始连续的可用集合中不多于 K 张邮票贴出的邮资数。

SAMPLE INPUT
(file stamps.in)

5 2

1 3 

SAMPLE OUTPUT
(file stamps.out)

13