AT_abc192_f [ABC192F] Potion

题目描述

有 $N$ 种素材，第 $i$ 种素材具有 $A_i$ 的魔力值。

魔法使高桥君打算从中选择至少一种素材进行合成，制作出药水。

如果用 $k$ 种素材合成药水，则药水在合成后的初始魔力值为所选素材的魔力值之和，并且每经过 $1$ 单位时间，魔力值会增加 $k$。注意，魔力值的增加是离散的，而不是连续的。

高桥君只允许在时刻 $0$ 合成一次素材。请问，最早在什么时候可以获得魔力值恰好为 $X$ 的药水？

可以证明，在给定的约束下，一定存在能够合成出魔力值恰好为 $X$ 的药水的方法。

输入格式

输入通过标准输入给出，格式如下：

$N\ X\ A_1\ \ldots\ A_N$

输出格式

输出能够获得魔力值恰好为 $X$ 的药水的最早时刻。

输入输出样例 #1

输入 #1

3 9999999999
3 6 8

输出 #1

4999999994

输入输出样例 #2

输入 #2

1 1000000000000000000
1

输出 #2

999999999999999999

说明/提示

限制条件

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 10^7$
• $10^9 \leq X \leq 10^{18}$
• 所有输入均为整数

样例解释 1

如果合成素材 $1$ 和素材 $3$，则药水在时刻 $0$ 的魔力值为 $3+8=11$，每经过 $1$ 单位时间，魔力值增加 $2$，因此在时刻 $4999999994$ 时魔力值为 $9999999999$，这是最早的时刻。
如果合成素材 $1,2,3$，则药水在时刻 $3333333327$ 时魔力值为 $9999999998$，在时刻 $3333333328$ 时魔力值为 $10000000001$，无法恰好得到 $9999999999$。

由 ChatGPT 4.1 翻译