Binary Search on the Answer

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$.

You may perform operations on this sequence: in one operation, choose one element and increase it by $1$. After at most $k$ operations, you want to maximize the minimum value of the sequence. What is this maximum possible minimum value?

Input Format

The first line contains two integers $n, k$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

Output one line containing a single integer: the answer.

Sample Input 1

5 10
1 4 2 6 8

Sample Output 1

5

Sample Input 2

1 10000000000000
100000000

Sample Output 2

10000100000000

Constraints

For $100\%$ of the test cases, $1 \le n \le 10^5$, $1 \le a_i \le 10^8$, $0 \le k \le 10^{13}$.

Hint

After finishing this problem, please ask the assistant teacher for the stage test of lesson 26.