#89. 砍树

砍树

题目描述

小华被大林叫去砍树,他需要砍倒 mm 米长的木材。现在,小华弄到了一个奇怪的伐木机。 伐木机工作过程如下:小华设置一个高度参数 hh(米),伐木机升起一个巨大的锯片到高度 hh, 并锯掉所有的树比 hh 高的部分(当然,树木不高于 hh 米的部分保持不变)。小华就得到树木被锯下的部分。 例如,如果一行树的高度分别为 20151020、15、101717 米,小华把锯片升到 1515 米的高度,切割后树木剩下的高度将是 15151015、15、101515 米,而小华将从第 11 棵树得到 55 米, 从第 44 棵树得到 22 米,共得到 77 米木材。 小华非常关注生态保护,所以他不会砍掉过多的木材。这正是他为什么要尽可能高地设定伐木机锯片的原因。 现在请你帮助小华找到伐木机锯片的最大的整数高度 hh,使得他能得到的木材至少为 mm 米。换句话说,如果再升高 11 米,则他将得不到 mm 米木材。

输入格式

第 1 行 2 个整数 nnmm, nn 表示树木的数量, mm 表示需要的木材总长度。
第 2 行 nn 个整数,表示每棵树的高度,值均不超过 10910^9。保证所有木材长度之和大于 mm, 因此必然有解。

输出格式

一行一个整数,表示砍树的最高高度。

样例

5 20
4 42 40 26 46
36

说明/提示

  • 对于 30%30\% 的数据:1n10,1m301\leq n \leq 10, 1\leq m \leq 30
  • 对于 70%70\% 的数据:1n103,1m1041\leq n \leq 10^3, 1\leq m \leq 10^4
  • 对于 100%100\% 的数据:1n106,1m2×1091\leq n \leq 10^6, 1\leq m \leq 2×10^9