CF725E Too Much Money

Alfred 想买一个售价为 $c$ 美元的玩具驼鹿。商店不找零，所以他必须恰好支付 $c$ 美元，不能多也不能少。他有 $n$ 枚硬币。为了用这些硬币凑出 $c$ 美元，他按照以下算法操作：设 $S$ 为当前已使用的硬币集合，初始为空。Alfred 会不断地从自己拥有的硬币里，选择面值最大且加入 $S$ 后总面值不超过 $c$ 的硬币，加入 $S$。如果没有这样可以加入的硬币，且 $S$ 中硬币总面值仍然小于 $c$，他就会放弃回家。注意，Alfred 一旦把硬币加入 $S$，就不会再拿出来。 作为程序员的你可能意识到，尽管存在一组硬币面值总和恰好为 $c$，Alfred 的算法依然可能失败。例如，如果 Alfred 有一枚 $3$ 元硬币、一枚 $4$ 元硬币和两枚 $5$ 元硬币，要买一个价值 $12$ 元的驼鹿时，他会先加入两枚 $5$ 元硬币，总值 $10$ 元，然后任何其他硬币都会让总值超过 $12$ 元，于是他无法凑出 $12$ 元而放弃。但实际上，如果他用 $3$、$4$、$5$ 各一枚，就能刚好达到 $12$。 Bob 想说服 Alfred 他的算法有问题但未成功。现在 Bob 想送 Alfred 一些硬币（可以是任何正整数面额，任意数量，可以重复），让 Alfred 的算法失败。Bob 希望这些新硬币总面值尽量小。请你求出他最少需要送出多少面值的硬币。如果无法实现（即无论怎么送，Alfred 的算法都不会失败），则输出 "Greed is good"。 你可以假设如果 Bob 不送任何硬币，Alfred 的算法总是能够成功。

第一行一个整数 $c$（$1 \leq c \leq 200000$），表示 Alfred 想支付的价格。 第二行一个整数 $n$（$1 \leq n \leq 200000$），表示 Alfred 最初拥有的硬币数量。 接下来 $n$ 行，每行一个整数 $x$（$1 \leq x \leq c$），表示 Alfred 拥有的一枚硬币的面值。

如果有解，输出可行方案中 Bob 送出的硬币总面值的最小值；否则，输出 "Greed is good"。

在第一个样例中，Bob 只需送 Alfred 一枚面值为 $5$ 的硬币，即可制造问题描述中的情况。 在第二个样例中，没有任何一组硬币能使 Alfred 的算法失败。 由 ChatGPT 5 翻译