Рабочее место участника

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

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

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

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

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

Во второй строке входного файла находятся `n` чисел `a_i` (`-10^4\ ≤\ a_i\ ≤\ 10^4`, `a_i\ ≠\ 0`) – программа робота.

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

4 1
1 2 -1 -3

5

7 2
5 -3 7 9 -2 -8 -1

29