댐 건설

강의 단면을 N개의 구간으로 나타낸 높이 배열이 있다. 댐을 높이 H로 설치하면 각 구간에서 H보다 낮은 부분이 물로 채워진다. 즉, i번째 구간의 물의 양은 max(0, H - height[i])이다.

댐 높이 H를 1~MAX로 이분 탐색하여 고이는 물의 총 양이 목표값 W 이상이 되는 최소 H를 구하시오.

입력

첫째 줄에 구간 수 N과 목표 물의 양 W가 주어진다. 둘째 줄에 N개의 구간 높이가 주어진다.

• 1 ≤ N ≤ 100,000
• 1 ≤ W ≤ 10^14
• 1 ≤ 각 높이 ≤ 10^9

출력

고이는 물의 양이 W 이상이 되는 최소 댐 높이 H를 출력한다.

예제 입력

7 15
6 4 3 8 5 2 6

예제 출력

6