문제 설명

디저트 가게 사장님이 진열대에 높이가 제각각인 케이크들을 세워 두었습니다. 사장님은 손님들을 위한 무료 시식 코너를 만들려고, 절단기의 칼날을 어떤 높이 H에 맞춰 케이크들을 '한 번에' 가로로 자릅니다. 그러면 H보다 높은 케이크는 윗부분이 잘려 나가고, 그 잘린 윗부분을 모두 모아 시식용 조각으로 씁니다. (H보다 낮은 케이크는 칼날에 닿지 않아 그대로 남습니다.) 칼날 높이 H가 낮을수록 더 많이 잘려 시식량은 늘지만 진열용 케이크가 망가집니다. 그래서 시식에 필요한 양은 딱 채우되, 진열대 손상을 최소화하도록 칼날을 최대한 높게 두고 싶습니다. 필요한 시식량 이상을 모을 수 있는 칼날 높이 H의 최댓값을 구하세요.

입력

출력

제약 조건

• •1 ≤ N ≤ 1,000,000
• •1 ≤ 각 케이크 높이 ≤ 1,000,000,000
• •1 ≤ M ≤ 2,000,000,000 (모든 케이크를 0 높이로 잘라도 항상 M 이상은 얻을 수 있음)

예제

6 18
15 22 9 18 30 25

19