题目描述

伐木工人 Mirko 需要获得至少 $M$ 米长的木材。

他面前有一排共 $N$ 棵树，第 $i$ 棵树的高度为 $h_i$。

Mirko 使用一台伐木机进行砍伐。首先，他需要设置一个整数高度 $H$，然后伐木机将锯片升到高度 $H$，并锯掉所有高度超过 $H$ 的树木中高于 $H$ 的部分。

如果一棵树的高度不超过 $H$，则不会被锯掉任何部分。

例如，一排树的高度分别为 $20,15,10,17$，若将锯片高度设置为 $15$，则砍伐后树木的高度分别变为：

$15,15,10,15$

此时可以获得的木材长度为：

((20-15)+(17-15)=7)

Mirko 希望尽可能少地砍伐树木，因此需要将锯片设置得尽可能高。

请找到最大的整数高度 $H$，使得砍伐后获得的木材总长度不少于 $M$。

换句话说，如果将锯片高度再升高 $1$，获得的木材总长度就会少于 $M$。

输入格式

第一行输入两个整数 $N$ 和 $M$，分别表示树木数量和需要获得的木材总长度。

第二行输入 $N$ 个整数 $h_1,h_2,\ldots,h_N$，表示每棵树的高度。

输出格式

输出一个整数，表示满足条件的最大锯片高度 $H$。

样例

4 7
20 15 10 17

15

5 20
4 42 40 26 46

36

数据范围

对于 $100$ 的测试数据：

$1 \le N \le 10^6$。

$1 \le M \le 2 \times 10^9$。

$h_i \le 10^9$。

所有树木高度之和大于 $M$。