C. Оптимальная сумма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Перед Вами вновь задача на массивы. Вам задан массив a состоящий из n целых чисел a1, a2, ..., an, а также целое положительное число len. Введем две характеристики для заданного массива.

  • Рассмотрим произвольный отрезок массива длины len, начинающийся в позиции i. Величину , назовем модульной суммой на выбранном отрезке. Другими словами, модульная сумма — это сумма чисел на выбранном отрезке длины len, взятая по модулю.
  • Величину назовем оптимальной суммой массива. Другими словами, оптимальная сумма массива — это максимальная из модульных сумм на всевозможных отрезках массива длины len.

В задаче от Вас требуется посчитать оптимальную сумму заданного массива a. Однако, прежде чем производить вычисления, Вам разрешено произвести не более k последовательных операций с этим массивом следующего вида: за одну операцию разрешается взять произвольное число массива ai и умножить его на -1. Другими словами, не более k раз разрешается взять произвольное число массива ai и заменить его на  - ai. Каждое число массива разрешается выбирать произвольное количество раз.

Требуется посчитать максимально возможную оптимальную сумму массива после выполнения не более k операций, указанных выше.

Входные данные

В первой строке заданы два целых числа n, len (1 ≤ len ≤ n ≤ 105) — количество элементов в массиве и длина выбираемого подотрезка массива, соответственно.

Во второй строке задана последовательность из n целых чисел a1, a2, ..., an (|ai| ≤ 109) — исходный массив.

В третьей строке задано единственное целое число k (0 ≤ k ≤ n) — допустимое количество операций.

Все числа в строках разделены ровно одним пробелом.

Выходные данные

В единственной строке выведите максимально возможную оптимальную сумму после выполнения не более k допустимых операций.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Примеры
Входные данные
5 3
0 -2 3 -5 1
2
Выходные данные
10
Входные данные
5 2
1 -3 -10 4 1
3
Выходные данные
14
Входные данные
3 3
-2 -5 4
1
Выходные данные
11