19769번 - Робот 다국어

문제

Компания <<Филипп индастриз>> отправила на Марс новый робот-марсоход. Целью робота является исследование поверхности Марса.

Для исследования Марса робот будет перемещаться по поверхности планеты на север и на юг вдоль прямой. Программа робота состоит из $n$ команд, каждая из которых описывается целым числом $a_i$. Каждое число $a_i$ задаёт количество шагов, которое необходимо сделать роботу. Если $a_i > 0,ドル то робот совершает $|a_i|$ шагов на север, если $a_i < 0,ドル то $|a_i|$ шагов на юг. Робот исполняет команды последовательно, начиная с первой.

Однако по пути на Марс робот подвергся космическому излучению и его программа могла повредиться. Запустив процедуру тестирования памяти, ученые выяснили, что в программу было внесено от 0 до $k$ ошибок следующего вида: число $a_i$ оказалось заменено на $-a_i$. Тем не менее, приземлившись на Марс, робот выполнил свою, возможно поврежденную, программу.

Теперь для организации спасения робота ученые хотят выяснить, насколько далеко от точки, в которой он начал выполнение программы, робот мог оказаться в результате. Помогите им это выяснить.

입력

В первой строке входного файла находятся два числа $n,ドル $k$ (1ドル \le k \le n \le 10^5$) --- количество чисел в программе робота и максимальное количество ошибок.

Во второй строке входного файла находятся $n$ чисел $a_i$ ($-10^4 \le a_i \le 10^4,ドル $a_i \ne 0$) --- программа робота.

출력

В единственной строке выходного файла выведите максимальное расстояние в шагах, на которое мог удалиться робот, выполнив все команды и совершив не более $k$ ошибок.

제한

힌트

В первом примере робот мог, например, выполнить программу 1,ドル 2, -1, 3$ и в результате удалиться на 5 шагов на север.