CF183E Candy Shop

著名的 Codeforces 幼儿园共有 $n$ 个小朋友，编号从 $1$ 到 $n$。他们每个人都从父母那里获得了若干卢布的零花钱。 今天，他们将前往镇上最有名的糖果店。糖果店出售的糖果采用包装发售：对于所有 $1$ 到 $m$ 的整数 $i$，店内售卖含有恰好 $i$ 颗糖果的糖果包。每颗糖果售价为 $1$ 卢布，所以一个包含 $x$ 颗糖果的糖果包价格为 $x$ 卢布。 小朋友们轮流购买糖果包，从第 $1$ 个小朋友开始。在一个回合中，第 $i$ 个小朋友会购买一个糖果包。由于 Codeforces 幼儿园竞争激烈，在每个回合中，小朋友购买的糖果包所含的糖果数量必须**严格大于**前一个回合所购糖果包中的糖果数量（第一个回合例外：第一个孩子可以买任意一个包装）。然后，下一回合轮到编号为 $i+1$ 的小朋友，如果是第 $n$ 个，则下一位又变为第 $1$ 个。这个过程可以在任意时刻结束，但结束时，所有孩子都必须买到**相同数量**的糖果包。且任何小朋友购买糖果花费的总金额不能超过其零花钱。 你是糖果店的工作人员，希望为孩子们预备糖果。请你输出糖果店可以卖出的最多糖果数量。如果因为零花钱不足无法买糖果，请输出 $0$。

第一行包含两个正整数 $n$ 和 $m$，分别表示小朋友的人数和糖果店出售单包最大糖果数。$2 \leq n \leq 2 \cdot 10^{5}$，$2 \leq m \leq 5 \cdot 10^{6}$，且 $n \leq m$。 接下来 $n$ 行，每行一个正整数，表示每个小朋友的零花钱（单位：卢布）。零花钱的数值不会超过 $10^{18}$，输入顺序按照小朋友编号从 $1$ 到 $n$。

输出糖果店最多可以卖出的糖果数量。

对于第一个样例，能够买到 $13$ 颗糖果的一种方案如下： - 第 1 回合，第 1 个小朋友购买了 1 颗糖果。 - 第 2 回合，第 2 个小朋友购买了 3 颗糖果。 - 第 3 回合，第 1 个小朋友购买了 4 颗糖果。 - 第 4 回合，第 2 个小朋友购买了 5 颗糖果。 由 ChatGPT 5 翻译