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 taka. With 1 taka you can increase the height of the a building by 1. So you want to spend k taka in such a way that after spending k taka the height of the lowest building will be maximized.

Input

First line of the input will consist of two integers n the number of buildings and k the amount of taka you have. The next line will consist of n integers the height of the buildings. (1<=n<=105 and 0<=k , 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