Maximize the Array Sum After Negating at Most K Elements

Given an array A of integers and an integer K, you may negate up to K elements of the array. Return the maximum value of the smallest prefix sum after the operations (or equivalently, maximize the array configuration so all prefix sums are positive).

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ N
• -10⁹ ≤ A[i] ≤ 10⁹

Example 1

Input:

A = [4, 1, 1, 1]

Output:

3

Explanation: We can apply only at-most 3 negate operations, to make A = [4, -1, -1, -1], after the negate operation, The prefix sums of A, p(A) = [4, 3, 2, 1] which are all positive. So that the answer for A is 3.