P6984 [NEERC 2015] Landscape Improved

路易斯 $L$ Le Roi-Univers 下令改善从皇宫看到的景观。陛下希望看到一座高山。 首席景观经理打算为路易斯建造一座山。他将景观表示为单位方格网格上的平面图。一些方格已经被岩石填满，而其他方格是空的。这大大简化了设计。单位方格足够小，从皇宫看去，景观似乎是平滑的。 首席景观经理有一个景观计划——每个单位宽度的所有岩石填充列的高度。他打算在现有景观上最多添加 $n$ 个单位方格的石头，以建造一座尽可能高的山峰。不幸的是，石头堆非常不稳定。一个单位方格的石头只能精确地放在其他填充的石头或岩石方格的正上方，而且其左下方和右下方的方格应该已经被填满。 现有景观 改进后的景观 你的任务是帮助首席景观经理确定他能建造的最高山峰的最大高度。

输入文件的第一行包含两个整数 $w$ ——现有景观的宽度和 $n$ ——最多可以添加的石头方格数 $(1 \le w \le 100 000 , 0 \le n \le 10^{18})$。 接下来的 $w$ 行中的每一行包含一个整数 $h_{i}$ ——现有景观列的高度 $(1 \le h_{i} \le 10^{9})$。

输出文件应包含一个整数——在最多添加 $n$ 个单位方格的石头后，景观可能达到的最大高度。

时间限制：1 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。