You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $N$ 个人参加某个活动，第 $i$ 个人的交通费用为 $A_i$ 日元。

作为活动主办者的高桥君设定了交通费补助的上限 $x$，对于第 $i$ 个人，将给予 $\min(x, A_i)$ 日元的交通费补助。这里 $x$ 必须是非负整数。

高桥君的预算为 $M$ 日元，他希望给予 $N$ 个人的交通费补助总和不超过 $M$ 日元。在满足预算条件的情况下，交通费补助上限 $x$ 最大可以是多少？

如果交通费补助上限可以无限大，请输出相应的信息。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出满足预算条件的交通费补助上限 $x$ 的最大值。如果交通费补助上限可以无限大，请输出 infinite。

输入输出样例 #1

输入 #1

4 8
1 3 2 4

输出 #1

2

输入输出样例 #2

输入 #2

3 20
5 3 2

输出 #2

infinite

输入输出样例 #3

输入 #3

10 23
2 5 6 5 2 1 7 9 7 2

输出 #3

2

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^{14}$
• $1 \leq A_i \leq 10^9$
• 输入的所有数值均为整数

样例解释 1

当交通费补助上限为 $2$ 日元时，$N$ 个人获得的交通费补助总和为 $\min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7$ 日元，不超过预算 $8$ 日元。当交通费补助上限为 $3$ 日元时，$N$ 个人获得的交通费补助总和为 $\min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9$ 日元，超过了预算 $8$ 日元。因此，交通费补助上限的最大值为 $2$ 日元。

样例解释 2

交通费补助上限可以无限大。

由 ChatGPT 4.1 翻译