Binary Search the Answer

Problem Description

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

You may perform operations on this sequence; each operation selects one element and adds $1$ to it. After at most $k$ operations, you want the minimum value of the sequence to be as large as possible. What is that maximum achievable minimum value?

Input Format

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

Output Format

Output one line containing an 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 data, $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^8, 0 \leq k \leq 10^{13}$.

Hint

• After finishing this problem, please ask the teaching assistant for the $26$-th stage test.