떡볶이 떡 만들기

N개의 떡이 있다. 절단기 높이를 H로 설정하면 H보다 높은 떡은 H까지 잘리고, H 이하인 떡은 그대로 남는다. 잘린 떡의 합이 M 이상이 되도록 하는 H의 최댓값을 구하라.

H=0이면 모든 떡이 잘리므로 항상 M 이상을 얻을 수 있음이 보장된다.

입력

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에 N개의 떡 높이가 공백으로 구분되어 주어진다. (0 ≤ 높이 ≤ 1,000,000,000)

출력

절단기 높이의 최댓값을 출력하라.

예제 입력 1

4 6
19 15 10 17

예제 출력 1

15