/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
あるイベントには 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
Score : 300 points
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