Problem Description

Lumberjack Mirko needs to cut $M$ meters of wood. This is an easy task for Mirko because he has a brand new lumberjack machine that can cut through the forest like wildfire. However, Mirko is only allowed to cut a row of trees.

The operation of Mirko's lumberjack machine is as follows: Mirko sets a height parameter $H$ (in meters), and the machine raises a giant sawblade to height $H$, cutting off all parts of the trees that are taller than $H$ (of course, parts of the trees that are not taller than $H$ remain unchanged). Mirko then collects the cut-off parts of the trees. For example, if the heights of a row of trees are $20, 15, 10,$ and $17$, and Mirko sets the sawblade to $15$ meters, the remaining heights of the trees after cutting will be $15, 15, 10,$ and $15$, and Mirko will get $5$ meters from the first tree and $2$ meters from the fourth tree, totaling $7$ meters of wood.

Mirko is very concerned about ecological protection, so he does not cut more wood than necessary. This is also why he sets the sawblade as high as possible. Help Mirko find the maximum integer height $H$ of the sawblade such that he can get at least $M$ meters of wood. In other words, if he raises the sawblade by $1$ more meter, he will not get $M$ meters of wood.

Input Format

The first line contains two integers $N$ and $M$, where $N$ is the number of trees and $M$ is the total length of wood needed.

The second line contains $N$ integers representing the height of each tree.

Output Format

A single integer representing the maximum height of the sawblade.

Sample Input and Output

Sample Input #1

4 7
20 15 10 17

Sample Output #1

15

Sample Input #2

5 20
4 42 40 26 46

Sample Output #2

36

Notes

For $100\%$ of the test data, $1 \le N \le 10^6$, $1 \le M \le 2 \times 10^9$, the height of the trees $\le 4 \times 10^5$, and the total height of all trees is greater than $M$.

见题面 Input 部分

见题面 Output 部分