/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ N の数列 A = (A_1, A_2, \ldots, A_N) と整数 K が与えられます。
あなたは次の操作を 0 回以上 K 回以下行うことができます。
- 1 \le i \le N を満たす整数 i を 1 つ選び、A_i に i を加える。
操作後の数列に対する \displaystyle \min_{1 \le i \le N} A_i としてありうる最大値を求めてください。
制約
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^{18}
- 1 \le K \le 10^{18}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 3 1 2 3
出力例 1
3
例えば i = 1 を 2 回、 i = 2 を 1 回選ぶと、数列は (3, 4, 3) になります。このとき最小値は 3 です。
最小値を 4 以上にすることはできないため、 3 と出力して下さい。
入力例 2
4 5 10 1 10 1
出力例 2
7
入力例 3
20 457 8 9 10 9 8 8 4 6 8 1 5 10 2 8 2 6 8 1 6 6
出力例 3
132
Score : 400 points
Problem Statement
You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N and an integer K.
You can perform the following operation between 0 and K times, inclusive.
- Choose an integer i satisfying 1 \le i \le N, and add i to A_i.
Find the maximum possible value of \displaystyle \min_{1 \le i \le N} A_i for the sequence after the operations.
Constraints
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^{18}
- 1 \le K \le 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
3 3 1 2 3
Sample Output 1
3
For example, by choosing i = 1 twice and i = 2 once, the sequence becomes (3, 4, 3). In this case, the minimum value is 3.
It is impossible to make the minimum value 4 or greater, so output 3.
Sample Input 2
4 5 10 1 10 1
Sample Output 2
7
Sample Input 3
20 457 8 9 10 9 8 8 4 6 8 1 5 10 2 8 2 6 8 1 6 6
Sample Output 3
132