A Little Cheating Never Hurt Anybody

After finding out the evil plan of cheater Kayaba Akihiko, Kirito caught him and started a duel.

Both of them are extremely overpowered. That's why Kirito will only be able to strike Kayaba once before being evaporated. Kirito has an array $p$ of $n$ different power-ups. The power of the attack is defined as the maximal subarray sum of the array $p$.

Kayaba is a very experienced cheater, so he knew Kirito's plan. That's why he can perform the following operation $k$ times:

• choose an index $i$ $(1\le i\le n)$ and decrease the value of $p_i$ by one.

Your task is to predict the minimal possible power of Kirito's attack after Kayaba's cheating.

The maximal subarray sum is the maximum sum of values in a contiguous, nonempty subarray. For example, for the array $[1,-2,4,3,-5,10]$, the subarray from $3$ to $6$ has the maximum subarray sum, because $a_3+a_4+a_5+a_6=4+3+(-5)+10=12$ is the largest sum among all the subarrays.

Input

The first line contains two integers $n$ and $k$ ($1\le n\le 5\cdot 10^5,0\le k\le 10^9$) — size of the array and the number of operations Kayaba can perform.

The second line contains $n$ integers $p_1,p_2,\dots ,p_n$ ($-10^9\le p_i\le 10^9$) — elements of the array.

Output

Output a single integer — minimized maximum subarray sum.

Examples

Note

In the first example, Kayaba cannot perform any operations, so the array remains unchanged. Maximal subarray sum will be the sum of the entire array $1+2+3+4+5=15$.

In the second example, Kayaba can reduce the value of any element by $1$, and the maximal subarray sum will be $8$.

In the third example, Kayaba can reduce the first and the last element by $1$ resulting in the array $[3,-4,-4,3]$, where the maximum subarray sum is $3$.

Scoring

1. ($3$ points): $k=0$;

2. ($6$ points): $k=1$;

3. ($6$ points): $p_i\ge 0$;

4. ($17$ points): $n\le 1000$;

5. ($33$ points): $n\le 10^5$;

6. ($35$ points): without additional constraints.