Перед Вами вновь задача на массивы. Вам задан массив a состоящий из n целых чисел a1, a2, ..., an, а также целое положительное число len. Введем две характеристики для заданного массива.
- Рассмотрим произвольный отрезок массива длины len, начинающийся в позиции i. Величину
, назовем модульной суммой на выбранном отрезке. Другими словами, модульная сумма — это сумма чисел на выбранном отрезке длины len, взятая по модулю. - Величину
назовем оптимальной суммой массива. Другими словами, оптимальная сумма массива — это максимальная из модульных сумм на всевозможных отрезках массива длины len.
В задаче от Вас требуется посчитать оптимальную сумму заданного массива a. Однако, прежде чем производить вычисления, Вам разрешено произвести не более k последовательных операций с этим массивом следующего вида: за одну операцию разрешается взять произвольное число массива ai и умножить его на -1. Другими словами, не более k раз разрешается взять произвольное число массива ai и заменить его на - ai. Каждое число массива разрешается выбирать произвольное количество раз.
Требуется посчитать максимально возможную оптимальную сумму массива после выполнения не более k операций, указанных выше.
Выходные данные
В единственной строке выведите максимально возможную оптимальную сумму после выполнения не более k допустимых операций.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
0 -2 3 -5 1
2
|
10
|
|
2
|
5 2
1 -3 -10 4 1
3
|
14
|
|
3
|
3 3
-2 -5 4
1
|
11
|