#P7010. 砍树

砍树

Description

在一片树林里, 有 N 颗树,你需要砍下 M 米的木头.

仅有一排树木可以供你砍伐

伐木机的工作原理如下:设置高度参数 H(以米为单位),机器将一个巨大的锯片提升到那个高度,并切断高于 H 的所有树木部分(当然,不高于 H 米的树木仍然完好无损).

例如:

如果有一排树木高度为 20,15,10 和 17 米,参数设为 15 米,

切割后剩余的树的 高度将是 15,15,10 和 15 米,得到的木头为第一棵树的 5 米和第四棵树的 2 米,总共 7 米。

因为提倡生态意识,所以不能砍下不必要的木头。

这就是为什么要把锯条尽可能地抬高。

请你找到最大的整数高度的锯片,使得你砍下至少 M 米的木头..

Format

Input

第一行包含两个空格分隔的正整数,N(1≤N≤1 000 000),M(1≤M≤2 000 000 000),含 义见题面.

第二行输入包含 N 个空格分隔的小于 1000000 的正整数.

第 i 个正整数表示第 i 棵的 高度.

保证所有树的高度和大于 M..

Output

一行一个正整数 H,即可以获得 M 米木材的前提下,设置锯片的最大高度

Samples

输入数据1

4 7
20 15 10 17

输出数据1

15

Limitation

250ms, 1024KiB for each test case.