Statement

Andrei and Alex are playing a game with an array V of N elements. Andrei can perform at most K operations on the array. In each operation, he can decrease any element of the array by 1. After performing these operations, Andrei must pay Alex S dollars, where S is the maximum subarray^* sum of the modified array. The subarray must contain at least one element. Since Andrei wants to pay as little as possible, he chooses his operations optimally to minimize S. Given N, K and the array V, what is the minimum amount of money Andrei will have to pay Alex? ^* An array b is a subarray of an array a if b can be obtained from a by deletion of several (possibly, zero) elements from the beginning and several (possibly, zero) elements from the end. In particular, an array is a subarray of itself.