← 返回题目列表

Codeforces · 725/E

E. 钱太多

中文机器翻译题面 查看原题

Alfred 想买一只价值 c 美元的玩具驼鹿。商店不给零钱,所以他必须给商店正好c美元,不能多也不能少。他有n个硬币。为了从他的硬币中赚取 c 美元,他遵循以下算法:令 S 为正在使用的硬币集合。 S 最初是空的。 Alfred不断地将他拥有的价值最高的硬币添加到S中,使得添加硬币后S中的硬币总价值不超过c。如果没有这样的硬币,并且S中硬币的价值仍然小于c,他放弃并回家。请注意,Alfred 在添加硬币后绝不会从 S 中取出硬币。

作为一名程序员,您可能会意识到,即使存在一组价值恰好为 c 的硬币,阿尔弗雷德的算法也可能会失败。例如,如果阿尔弗雷德有一枚价值 3 美元的硬币,一枚价值 4 美元的硬币和两枚价值 5 美元的硬币,而驼鹿的价格为 12 美元,那么阿尔弗雷德会将两枚 5 美元的硬币添加到 S 中,然后放弃,因为添加任何其他硬币都会导致 S 中硬币的价值超过 12 美元。当然,Alfred 也可以将一枚 3 美元硬币、一枚 4 美元硬币和一枚 5 美元硬币组合起来以达到总数。

鲍勃试图说服阿尔弗雷德他的算法有缺陷,但阿尔弗雷德不相信他。现在鲍勃想给阿尔弗雷德一些硬币(除了阿尔弗雷德已经拥有的硬币之外),这样阿尔弗雷德的算法就会失败。鲍勃可以给阿尔弗雷德任何数量、任何面额的硬币(但受到每个硬币必须价值正整数美元的限制)。单一面额的硬币可以有多种。他想尽量减少他送给阿尔弗雷德的硬币的总价值。请找出这个最小值。如果没有解决方案,则打印“Greed is good”。您可以假设答案(如果存在)是肯定的。换句话说,如果鲍勃不给他任何硬币,阿尔弗雷德的算法就会起作用。

输入

第一行包含 c (1 ≤ c ≤ 200 000) — Alfred 想要支付的价格。第二行包含 n (1 ≤ n ≤ 200 000) — Alfred 最初拥有的硬币数量。接下来是 n 行,每行包含一个整数 x (1 ≤ x ≤ c),表示阿尔弗雷德一枚硬币的价值。

输出

如果有解决方案,请打印解决方案中硬币的最小可能总价值。否则,打印“Greed is good”(不带引号)。

示例

输入 #1

12
3
5
3
4

输出 #1

5

输入 #2

50
8
1
2
4
8
16
37
37
37

输出 #2

Greed is good

注意

在第一个示例中,Bob 应该给 Alfred 一枚价值 5 美元的硬币。这会产生问题陈述中描述的情况。

在第二个样本中,没有一组硬币会导致 Alfred 的算法失败。