Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Buildings

Limits 1s, 512 MB

There are n buildings in a row. The height of the i’th building is hi.

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

Input

The first line of the input will consist of two integers n (1 ≤ n ≤ 105) the number of buildings and k (0 ≤ k ≤ 109) the amount of money you have. The next line will consist of n integers the height of the buildings (0 ≤ hi ≤ 109).

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

Discussion

Statistics


66% Solution Ratio

edge555Earliest, 5M ago

bisnu_sarkarFastest, 0.0s

naimulhasanLightest, 393 kB

Rajan_sustShortest, 318B

Submit

Login to submit

Related Contests