#P2725. [USACO3.1] 邮票 Stamps

    ID: 1669 远端评测题 1000ms 125MiB 尝试: 1 已通过: 1 难度: 3 上传者: 标签>动态规划dp搜索模拟背包贪心USACO

[USACO3.1] 邮票 Stamps

题目描述

给一组 nn 枚邮票的面值集合和一个上限 kk —— 表示信封上能够贴 kk 张邮票。请求出最大的正整数 mm,满足 11mm 的面值都可以用不超过 kk 张邮票表示出来。

输入格式

输入的第一行是两个整数,分别代表邮票上限 kk 和邮票面值数 nn

自第二行起,除最后一行外,每行有 1515 个整数 aia_i ,最后一行的整数个数不超过 1515,共有 nn 个整数,第 ii 个整数代表第 ii 种邮票的面值 aia_i

输出格式

输出一行一个整数代表 mm。若 mm 不存在请输出 00

5 2
1 3
13

提示

样例输入输出 1 解释

11 分和 33 分的邮票;你最多可以贴 55 张邮票。很容易贴出 1155 分的邮资(用 11 分邮票贴就行了),接下来的邮资也不难:

  • 6=3+36 = 3 + 3
  • 7=3+3+17 = 3 + 3 + 1
  • 8=3+3+1+18 = 3 + 3 + 1 + 1
  • 9=3+3+39 = 3 + 3 + 3
  • 10=3+3+3+110 = 3 + 3 + 3 + 1
  • 11=3+3+3+1+111 = 3 + 3 + 3 + 1 + 1
  • 12=3+3+3+312 = 3 + 3 + 3 + 3
  • 13=3+3+3+3+113 = 3 + 3 + 3 + 3 + 1

然而,使用 5511 分或者 33 分的邮票根本不可能贴出 1414 分的邮资。因此,答案为 1313

数据规模与约定

对于 100%100\% 的数据,保证 1k2001 \leq k \leq 2001n501 \leq n \leq 501ai1041 \leq a_i \leq 10^4

说明

题目翻译来自 NOCOW。