#589. 邮票 Stamps

邮票 Stamps

题目描述

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

例如,假设有 1\red{1} 分和 3\red{3} 分的邮票;你最多可以贴 5\red{5} 张邮票。很容易贴出 1\red{1}5\red{5} 分的邮资(用 1\red{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\red{5}1\red{1} 分或者 3\red{3} 分的邮票根本不可能贴出 14\red{14 }分的邮资。因此,对于这两种邮票的集合和上限K=5\red{K=5},答案是 M=13\red{M=13}

小提示:因为14\red{14}贴不出来,所以最高上限是13\red{13}而不是15\red{15}

输入格式

1\red{ 1} 行: 两个整数,K\red{K}N\red{N}K1<=K<=200\red{K(1 <= K <= 200)}是可用的邮票总数。N1<=N<=50\red{N(1 <= N <= 50)}是邮票面值的数量。

2\red{2} 行 .. 文件末: N\red{N} 个整数,每行 15\red{15} 个,列出所有的 N\red{N} 个邮票的面值,每张邮票的面值不超过 10000\red{10000}

输出格式

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

样例

输入样例

5 2
1 3

输出样例

13

提示

对于 100%\red{100\%} 的数据,保证 1k2001n501ai104\red{1≤k≤200,1≤n≤50,1\leq a_i \leq 10^4}

统计

相关

在下列比赛中:

DP 练习