Informatica Online Judge

  나무 자르기 [1777 / 06F1]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 18   Total Tried : 64


The Champion of this Problem (C++) : gs15044 - ms / 406byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

경곽이는 $M$ 미터의 나무를 자르고자 한다.

경곽이에게 나무 자르는 것은 너무나도 쉬운 일이다.

특히 이번에 구입한 새로운 전기톱을 이용하려고 한다.

경곽이의 전기톱은 다음과 같이 작동한다.

전기톱에서 자르고자 하는 높이 값 $H$(미터)를 설정하며 H보다 높은 모든 나무 부분은 잘라지게 되며 잘려진 나무를 경곽이는 가져오게 된다.

예를 들어, 나무의 높이가 $20, 15, 10, 17$ 인 $4$ 그루의 나무가 있고 경곽이가 높이를 $15$로 설정해서 전기톱을 사용했다면 잘린 후의 나무의 높이는 $15, 15, 10, 15$ 미터가 된다.

첫 번째 나무에서 $5$미터, 네 번째 나무에서 $2$미터로 잘린 총 $7$미터의 나무를 가지게 된다.

경곽이는 필요 이상으로 나무를 자르는 것을 좋아하지 않으르모 톱날의 높이를 가능한 한 높게 설정하려고 한다.

적어도 $M$미터의 나무를 가져가기 위해서 전기톱에서 설정할 수 있는 최대 높이의 값을 구해서 경곽이를 도와주자.

Input

첫째 줄에 나무의 수 $N$과 경곽이가 필요로 하는 나무의 길이 $M$이 공백으로 입력된다.

둘째 줄에는 $N$개의 공백으로 구분된 나무의 높이가 주어진다.

나무의 높이의 합은 항상 $M$을 넘는다.


[입력값의 정의역]

$1≤ N ≤ 1,000,000$
$1≤ M ≤ 2,000,000,000$

Output

전기톱의 높이의 최대값을 출력한다.

IO Example

입력1
4 7
20 15 10 17

출력1
15

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]