디마와 블록 울타리

면접 대비

시간 제한2초메모리 제한1024 MB

요약

n개의 기둥 높이 a_i와 추가 블록 k개가 주어질 때, 모든 기둥을 최소 h 높이로 만들 수 있는 가장 큰 h를 구합니다.

난이도: 쉬움10점 중 3점
유형: 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

레하 <<프시흐>>가 디마에게 블록 세트를 선물했다. 디마는 어른이 다 된 나이였지만 크게 기뻐했다. 바타이스크에서는 이런 장난감을 한 번도 판 적이 없었기 때문이다.

입력

울타리는 한 줄로 늘어선 $n$ 개의 기둥으로 이루어져 있고, 각 기둥 위에 블록이 몇 개씩 쌓여 있다. 이런 기둥을 구간이라고 부른다. 구간의 높이는 그 안에 있는 블록의 개수다. 울타리를 개조하려고 디마는 일부 구간 위에 블록을 얹는다. 이미 있던 블록은 건드리지 않는다. 디마에게는 여분 블록이 $k$ 개 있다. 개조 후 디마가 얻을 수 있는 울타리 높이의 최댓값을 구하라. 울타리 높이는 가장 낮은 구간의 높이와 같다.

출력

첫 줄에 두 정수 $n$ 과 $k$ 가 주어진다 ( $1 \le n \le 10^5$ ; $1 \le k \le 10^9$ ). $n$ 은 블록 단위로 잰 울타리의 너비, $k$ 는 여분 블록의 개수다. 둘째 줄에는 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다 ( $1 \le a_i \le 10^9$ ). $a_i$ 는 각 구간의 높이다.

디마와 블록 울타리

개조 후 디마가 얻을 수 있는 울타리 높이의 최댓값 $h$ 를 한 줄에 출력한다.

예제2

예제 1
입력
```
3 3
1 2 3
```
예상 출력
```
3
```
예제 2
입력
```
4 6
1 2 2 1
```
예상 출력
```
3
```