Transit
Uzhlanida is strategically located at the intersection of key trade routes, one of which is used by a neighboring allied state to transport its unique heaters to other countries. At the border between Uzhlanida and this allied state, where the route begins, there is a checkpoint that a train carrying a large number of heaters passes through daily. Recently, the governments of these two allied countries have agreed on new regulations for the transit of heaters through Uzhlanida over the next N days. According to this agreement, a specific number m must be chosen as the maximum number of heaters allowed in one train. For each train carrying A[i] heaters, exactly A[i]-m units of foreign products will be unloaded (if A[i] > m; otherwise, the train will pass without stopping and nothing will be unloaded). This unloading serves as a fee for the train's passage through Uzhlanida, covering the costs of maintaining the railway infrastructure. The total number of heaters unloaded in Uzhlanida over N days must be at least K to prevent economic losses.
The number of heaters in the train for each of the N days is predetermined (as per the contract). Determine the maximum number m that ensures Uzhlanida does not incur economic losses.
Input Format:
The first line contains two numbers N, K (1 ≤ N ≤ 10^6, 1 ≤ K ≤ 2 *10^9). The second line contains N numbers, representing the number of heaters in the train for each of the N days, with each number not exceeding 10^9.
Output Format:
Output a single number on one line – the solution to the problem. It is guaranteed that a solution always exists.
Explanation of the example:
There are 4 trains passing through Uzhlanida with 11, 6, 1, and 8 heaters respectively. To avoid losses, at least 7 heaters need to be unloaded. The maximum possible m that satisfies this requirement is 6, resulting in 5, 0, 0, and 2 heaters being unloaded from the trains, respectively, totaling 7, which meets the condition.