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.