Subarray-D

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$.

$^*$ 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.

Task

Given $N$, $K$ and the array $V$, what is the minimum amount of money Andrei will have to pay Alex?

Input data

The first line contains two integers, $N$ and $K$. The second line contains $N$ integers $V_i$.

Output data

You need to write a single line with an integer: the value $S$.

Constraints and clarifications

• $1 \le N \le 200 \ 000$.
• $0 \le K \le 10^9$.
• $-10^9 \le V_i \le 10^9$ for each $i=0\ldots N-1$.

Example 1

stdin

5 2
-1 2 3 -1 4

stdout

6

Explanation

In the first sample case, you can decrease the fifth element two times.

Example 2

stdin

6 7
-2 2 2 3 0 4

stdout

4

Explanation

In the second sample case, you can decrease the fourth element seven times.