Задача №113638. Робот
Компания «Филипп индастриз» отправила на Марс новый робот-марсоход. Целью робота является исследование поверхности Марса.
Для исследования Марса робот будет перемещаться по поверхности планеты на север и на юг вдоль прямой. Программа робота состоит из \(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 шагов на север.
4 1 1 2 -1 -3
5
7 2 5 -3 7 9 -2 -8 -1
29