Dima and the Construction Set

Interview

Time limit2sMemory limit1024 MB

Summary

Given n stack heights a_i and k extra pieces, find the largest h such that every stack can be raised to at least h.

Level: Easy3 of 10
Topics: Binary search, Greedy
Solved: No attempts yet

Problem

Leha <> gave Dima a construction set. Dima is well past childhood, yet he was delighted, since such toys had never been sold in Bataysk.

Input

The fence is a row of $n$ pieces, and on each piece some more pieces are stacked. Call such a stack a segment. The height of a segment is the number of pieces in it. To upgrade the fence, Dima places pieces on top of some segments. He does not touch pieces that are already there. Dima has $k$ extra pieces. Find the maximum height the fence can reach after the upgrade. The height of the fence equals the height of its shortest segment.

Output

The first line contains two integers $n$ and $k$ ( $1 \le n \le 10^5$ ; $1 \le k \le 10^9$ ), the width of the wall in pieces and the number of extra pieces. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ), the height of each segment.

Dima and the Construction Set

Print one integer $h$ , the maximum height of the fence Dima can get after the upgrade.

Examples2

Example 1
Input
```
3 3
1 2 3
```
Expected output
```
3
```
Example 2
Input
```
4 6
1 2 2 1
```
Expected output
```
3
```