P1873 [COCI 2011/2012 #5] EKO / Cutting Trees

Lumberjack Mirko needs to cut $M$ meters of wood. This is easy for Mirko because he has a shiny new woodcutting machine that can cut through a forest like wildfire. However, Mirko is allowed to cut only one row of trees. The machine works as follows: Mirko sets a height parameter $H$ (in meters), the machine raises a huge saw blade to height $H$, and it cuts off the part of every tree that is higher than $H$ (of course, trees not higher than $H$ remain unchanged). Mirko then collects the cut-off parts. For example, if a row of trees has heights $20, 15, 10$ and $17$, and Mirko raises the blade to $15$ meters, after cutting the remaining heights will be $15, 15, 10$ and $15$, and Mirko will get $5$ meters from the $1$st tree and $2$ meters from the $4$th tree, $7$ meters in total. Mirko cares about the environment, so he will not cut more wood than necessary. This is why he sets the saw blade as high as possible. Help Mirko find the maximum integer height $H$ such that the amount of wood he obtains is at least $M$ meters. In other words, if he raised it by $1$ meter more, he would not obtain $M$ meters of wood.

The first line contains two integers $N$ and $M$, where $N$ is the number of trees and $M$ is the required total length of wood. The second line contains $N$ integers, the heights of the trees.

Output a single integer, the highest possible blade height.

For $100\%$ of the testdata, $1 \le N \le 10^6$, $1 \le M \le 2 \times 10^9$, tree height $\le 4 \times 10^5$, and the sum of all tree heights $> M$. Translated by ChatGPT 5