EKO

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ trees with heights $h_i$. A saw set at integer height $H$ cuts off the part above $H$, producing $\sum_{i=1}^{N}\max(0,h_i-H)$ units of wood. Find the maximum $H$ that still produces at least $M$ units.

Input

The first line contains $N,M$. The second line contains the tree heights.

Output

Print the maximum valid saw height.

Subtasks

• Subtask 1 — 20%: $1\le N\le1000$.
• Subtask 2 — 30%: $1\le N\le10^5$.
• Subtask 3 — 50%: $1\le N\le10^6$, $1\le M\le2\cdot10^9$, $1\le h_i<10^9$. The sum of all heights is greater than $M$.

Examples

Input

4 7
20 15 10 17

Output

15

Explanation

At $H=15$ we obtain $5+2=7$ units. At $H=16$ we obtain only $5$, so $15$ is optimal.