103652: [Atcoder]ABC365 C - Transportation Expenses

Problem Statement

There are $N$ people participating in an event, and the transportation cost for the $i$-th person is $A_i$ yen.

Takahashi, the organizer of the event, decided to set a maximum limit $x$ for the transportation subsidy. The subsidy for person $i$ will be $\min(x, A_i)$ yen. Here, $x$ must be a non-negative integer.

Given that Takahashi's budget is $M$ yen, and he wants the total transportation subsidy for all $N$ people to be at most $M$ yen, what is the maximum possible value of the subsidy limit $x$?

If the subsidy limit can be made infinitely large, report that instead.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^{14}$
• $1 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_{N}$

Output

Print the maximum value of the subsidy limit $x$ that satisfies the budget condition, as an integer.

If the subsidy limit can be made infinitely large, print infinite instead.

Sample Input 1

4 8
1 3 2 4

Sample Output 1

2

If the subsidy limit is set to $2$ yen, the total transportation subsidy for all $N$ people is $\min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7$ yen, which is within the budget of $8$ yen.

If the subsidy limit is set to $3$ yen, the total transportation subsidy for all $N$ people is $\min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9$ yen, which exceeds the budget of $8$ yen.

Therefore, the maximum possible value of the subsidy limit is $2$ yen.

Sample Input 2

3 20
5 3 2

Sample Output 2

infinite

The subsidy limit can be made infinitely large.

Sample Input 3

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

Sample Output 3

2

问题陈述

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

活动的组织者高桥决定为交通补贴设置一个最大限额$x$。第$i$个人的补贴将是$\min(x, A_i)$日元。这里，$x$必须是一个非负整数。

已知高桥的预算是$M$日元，他希望所有$N$人的总交通补贴不超过$M$日元，补贴限额$x$的最大可能值是多少？

如果补贴限额可以无限增大，请报告这一点。

约束条件

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

输入

输入从标准输入以以下格式给出：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_{N}$

输出

打印满足预算条件的补贴限额$x$的最大值，作为一个整数。

如果补贴限额可以无限增大，打印infinite。

示例输入1

4 8
1 3 2 4

示例输出1

2

如果补贴限额设置为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

3 20
5 3 2

示例输出2

infinite

补贴限额可以无限增大。

示例输入3

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

示例输出3

2