该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

伐木工人米尔科需要砍倒总长度至少为 $M$ 米的木材。对他来说这并不困难，因为他有一台强力的伐木机，不过这台机器只能对一行树木进行统一高度的切割。

伐木机的工作方式如下：

• 米尔科设置一个整数高度参数 $H$（单位：米）；
• 伐木机会将所有高度超过 $H$ 的树木部分锯掉，使其剩余高度恰好为 $H$；
• 高度不超过 $H$ 的树木保持不变；
• 米尔科可以收集所有被锯下来的木材。

例如，一行树木的高度分别为 $20, 15, 10, 17$，若设定 $H = 15$， 切割后树木高度变为 $15, 15, 10, 15$， 获得的木材长度为 $(20-15) + (17-15) = 7$ 米。

米尔科非常注重生态保护，因此他希望在获得至少 $M$ 米木材的前提下，使锯片的高度 $H$ 尽可能大。

请你帮助米尔科找到满足条件的最大整数高度 $H$。 换句话说，若再将 $H$ 增加 $1$，则获得的木材总长度将严格小于 $M$。

格式

输入

• 第一行包含两个整数 $N$ 和 $M$：

  • $N$ 表示树木的数量（$1 \le N \le 10^6$）；
  • $M$ 表示所需木材的总长度（$1 \le M \le 10^9$）。

• 第二行包含 $N$ 个整数，表示每棵树的高度，均不超过 $10^9$。

保证所有树木高度之和大于 $M$，因此一定存在解。

输出

• 输出一个整数，表示砍树时锯片所能设置的最大高度 $H$。

样例

输入1

5 20
4 42 40 26 46

输出1

36