Transportation Expenses

题目描述

有 $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$。

4 8
1 3 2 4

2

3 20
5 3 2

infinite

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

2

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq M \leq 2 \times 10^{14}$ $1 \leq A_i \leq 10^9$ 所有输入值均为整数。如果补贴上限设为 $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$ 日元。
补贴上限可以被设为无限大。

标签: AtCoder|abc365C

来源

AtCoder|abc365C