Problem Description

You are given an integer array A of length N and a non-negative integer K.

You must perform exactly K operations. In each operation, you choose any index i and decrement the value A[i] by 1 (i.e., A[i] = A[i] - 1).

After all K operations have been performed, let min(A) be the minimum value currently present in the array. Your objective is to choose the operations in such a way that min(A) is maximized.

Return the maximum possible value of min(A) after exactly K operations.

Input

• A: An array of N integers.
• K: A non-negative integer representing the total number of decrements to perform.

Output

• An integer: The maximum achievable minimum value in the array after K operations.

Constraints

• 1 <= N <= 2 * 10^5
• -10^9 <= A[i] <= 10^9
• 0 <= K <= 10^18

Example

• A = [5, 1, 7], K = 3
  • One optimal strategy is to decrement 7 three times. The array becomes [5, 1, 4]. The minimum value min(A) is 1.
  • The answer is 1.