문제 설명
벌목꾼 충근이는 M 미터의 나무를 베어야 한다. 충근이에겐 순식간에 숲을 무너뜨릴 수 있는, 강력한 나무 자르는 기계를 가지고 있기 때문에 그리 어려운 일이 아니다.
하지만, 정부의 엄격한 숲 관리 때문에 충근이는 한 줄의 나무만 자를 수 있다.
충근이의 기계는 다음과 같이 동작한다. 충근이가 높이 H (미터)를 설정하면, 기계는 거대한 톱날을 설장한 높이 H 로 들어 올리고 H 보다 높은 모든 나무 부분을 잘라낸다.
그리고 나서 충근이는 잘려나간 부분들을 가져간다.
예를 들어, 한 줄에 높이가 20, 15, 10, 17 미터인 나무가 있고, 충근이가 높이를 15 로 설정했다면, 자르고 난 뒤 남은 나무 높이는 각각 15, 15, 10, 15가 되고, 충근이는 첫 번째 나무에서 5, 4번째 나무에서 2, 총 7 미터의 나무를 가져가게 된다.
충근이는 자연을 사랑하기 때문에 필요 이상으로 많은 나무를 자르고 싶지 않다. 그래서 기계의 높이를 가능한 최대로 설정하려고 한다.
충근이가 적어도 M 미터의 나무를 베어야 할 때, 기계를 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에는 나무의 수 $$N (1 ≤ N ≤ 1,000,000)$$ 과 충근이에게 필요한 나무의 높이 $$M (1 ≤ M ≤ 2,000,000,000)$$ 이 공백으로 구분되어 주어진다.
둘째 줄에는 각 나무의 높이(미터)가 공백으로 구분되어 N 만큼 주어진다. 나무의 높이는 $$1,000,000,000$$ 보다 작거나 같은 양의 정수이다.
주어진 모든 나무의 높이 합은 M을 초과하고, 충근이는 항상 필요한 양의 나무를 얻을 수 있다.
출력 설명
충근이가 기계를 설정할 수 있는 높이의 최댓값을 출력한다.