题目描述

伐木工人米尔科需要砍倒至少 M 米长的木材。米尔科在一行树木前，用伐木机把锯片升到高度 H（米），伐木机会把每棵树高于 H 的部分锯下，得到的木材为所有树上被锯下部分的总和（不高于 H 的树贡献 0）。米尔科希望尽可能把锯片升得高一些，同时保证至少能得到 M 米木材。求满足条件的最大整数高度 H（即把 H 再增加 1 就得不到至少 M 米木材）。

例如：树高为 20,15,10,17，H=15 时，得到木材为 (20-15)+(17-15)=5+2=7。

输入格式

• 第 1 行：两个整数 N 和 M，分别表示树的数量和所需木材总长度（1 ≤ N ≤ 1,000,000，1 ≤ M ≤ 2,000,000,000）。
• 第 2 行：N 个整数，表示每棵树的高度（每个高度 ≤ 1,000,000,000）。保证所有树的高度之和大于或等于 M（即解存在）。

输出格式

• 第 1 行：一个整数，表示满足至少得到 M 米木材的最大整数锯高 H。

输入样例 #1

5 20  
4 42 40 26 46

输出样例 #1

36

说明

在样例中，选择 H = 36 时，砍下的木材之和至少为 20；若把 H 增加到 37，则不能再得到至少 20 米木材。因此答案为 36。