Lumberjack and the Sawblade

Mirko is a dedicated lumberjack who needs to collect at least M meters of wood by cutting a row of trees with his new saw machine. The machine operates as follows: Mirko sets a height parameter \(H\) (in meters). The saw blade is raised to height \(H\) and cuts off the portions of all trees that exceed this height (trees with height less than or equal to \(H\) remain unchanged). For each tree with height \(a_i\), the wood obtained is \(\max(0, a_i - H)\) meters.

Mirko prefers to minimize environmental impact by cutting as little wood as necessary. Therefore, he wishes to set the saw blade as high as possible while still ensuring that he collects at least \(M\) meters of wood. In other words, \(H\) should be the largest integer such that the sum of wood collected is at least \(M\) meters. Note that if \(H\) were increased by 1, the total collected wood would drop below \(M\) meters.

Example: For tree heights of [20, 15, 10, 17] and \(M = 7\), if Mirko sets \(H = 15\), he gets \(\max(0,20-15) + \max(0,15-15) + \max(0,10-15) + \max(0,17-15) = 5 + 0 + 0 + 2 = 7\) meters of wood.

inputFormat

The first line contains two integers N and M (1 ≤ N ≤ 10⁶, 0 ≤ M ≤ 2×10⁹), where N is the number of trees and M is the minimum amount of wood needed in meters.

The second line contains N space-separated integers representing the heights of the trees. Each tree height is a positive integer not exceeding 10⁹.

outputFormat

Output a single integer representing the maximum integer height \(H\) at which to set the saw blade such that the wood collected is at least \(M\) meters.

sample

4 7
20 15 10 17

15