# 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≤i≤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≤n≤5⋅10_{5},0≤k≤10_{9}$) — size of the array and the number of operations Kayaba can perform.

The second line contains $n$ integers $p_{1},p_{2},…,p_{n}$ ($−10_{9}≤p_{i}≤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

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

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

($6$ points): $p_{i}≥0$;

($17$ points): $n≤1000$;

($33$ points): $n≤10_{5}$;

($35$ points): without additional constraints.