Трішки обману ніколи не зашкодить

Дізнавшись про зловісний план обманщика Каяби Акіхіко, Кіріто наздогнав його і почав поєдинок.

Обидва вони надзвичайно потужні. Тому Кіріто зможе вдарити Каябу лише один раз, перш ніж бути знищеним. У Кіріто є масив $p$ з $n$ різних підсилювачів. Сила атаки визначається як максимальна сума підмасиву масиву $p$.

Каяба - дуже досвідчений обманщик, тому він знав план Кіріто наперед. Перед атакою він може виконати наступну операцію $k$ разів:

• вибрати індекс $i$ $(1\le i\le n)$ та зменшити значення $p_i$ на одиницю.

Ваше завдання - передбачити мінімально можливу силу атаки Кіріто після дій Каяби.

Максимальна сума підмасиву - це максимальна сума значень в неперервному, непорожньому підмасиві. Наприклад, для масиву $[1,-2,4,3,-5,10]$, підмасив від $3$ до $6$ має максимальну суму підмасиву, оскільки $a_3+a_4+a_5+a_6=4+3+(-5)+10=12$ є найбільшою сумою серед усіх підмасивів.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $k$ ($1\le n\le 5\cdot 10^5,0\le k\le 10^9$) — розмір масиву та кількість операцій, які може виконати Каяба.

Другий рядок містить $n$ цілих чисел $p_1,p_2,\dots ,p_n$ ($-10^9\le p_i\le 10^9$) — елементи масиву.

Вихідні дані

Виведіть одне ціле число — мінімізовану максимальну суму підмасиву після операцій Каяби.

Приклади

Примітка

У першому прикладі Каяба не може виконати жодних операцій, тому масив залишається без змін. Максимальна сума підмасиву буде сумою всього масиву $1+2+3+4+5=15$.

У другому прикладі Каяба може зменшити значення будь-якого елемента на $1$, і максимальна сума підмасиву буде $8$.

У третьому прикладі Каяба може зменшити значення першого та останнього елементів на $1$, і масив стане рівним $[3,-4,-4,3]$, максимальна сума підмасиву дорівнює $3$.

Оцінювання

1. ($3$ бали): $k=0$;

2. ($6$ балів): $k=1$;

3. ($6$ балів): $p_i\ge 0$;

4. ($17$ балів): $n\le 1000$;

5. ($33$ бали): $n\le 10^5$;

6. ($35$ балів): без додаткових обмежень.