Tree Cutting

Interview

Time limit1sMemory limit256 MB

Summary

Binary search for the maximum saw height H so that trimming all trees above H yields at least M meters of wood total.

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

Problem

There are N trees standing in one row, and you need to take home at least M meters of wood in total.

If the cutter is set to height H, every tree taller than H is cut down to height H, and only the part above H is collected. Trees of height H or less are not cut. H may be any integer at least 0.

Find the maximum possible H that still lets you collect at least M meters of wood.

Input

The first line contains the number of trees N and the required wood length M.

1 <= N <= 1,000,000
1 <= M <= 2,000,000,000

The second line contains the heights of the N trees. Each height is an integer from 0 to 1,000,000,000, inclusive. The sum of all tree heights is always at least M.

Output

Print the maximum cutter height H that still lets you collect at least M meters of wood.

Examples2

Example 1
Input
```
4 7
20 15 10 17
```
Expected output
```
15
```
Example 2
Input
```
5 20
4 42 40 26 46
```
Expected output
```
36
```