Buildings

Replay of Codeware19: Int...
Limits 1s, 512 MB

There are n buildings in a row. The height of the ii-th building is hih_i.

You have k৳k. It is the amount of money you have. With 1৳1 you can increase the height of a building by 1. So you want to spend k৳k in such a way that after spending k৳k the height of the lowest building will be maximized.

Input

The first line of the input will consist of two integers nn (1n1051 ≤ n ≤ 10^5) the number of buildings and kk (0k1090 ≤ k ≤ 10^9) the amount of money you have. The next line will consist of nn integers the height of the buildings (0hi1090 ≤ h_i ≤ 10^9).

Output

Print a single integer the height of the lowest building.

Samples

InputOutput
5 10
1 2 3 4 5
5
InputOutput
1 10
10
20

Submit

Login to submit.

Contributors

Statistics

70% Solution Ratio
edge555Earliest, Sep '19
steinumFastest, 0.0s
steinumLightest, 5.5 kB
Rajan_sustShortest, 318B
Toph uses cookies. By continuing you agree to our Cookie Policy.