Рома работает в компании по продаже телевизоров. Сейчас ему нужно сдать отчет за прошедший год.
У Ромы есть список доходов компании, который представляет собой последовательность, состоящую из n целых чисел. Суммарный доход компании, это сумма всех чисел в последовательности. Рома решил провести ровно k замен знаков у некоторых чисел в последовательности. Причем у одного числа можно менять знак два и более раз.
Операцией замены знака у числа, называется операция умножения этого числа на -1.
Помогите Роме сделать замены так, что бы суммарный доход компании (сумма чисел в результирующей последовательности) был максимален. Обратите внимание, Рома должен провести ровно k замен.
Выходные данные
В единственную строку выведите ответ на задачу — максимальный суммарный доход, который можно получить после ровно k замен.
Примечание
В первом тесте можно получить последовательность [1, 1, 1], таким образом суммарный доход равен 3.
Во втором тесте оптимальнее всего получить последовательность [-1, 1, 1], таким образом суммарный доход равен 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
-1 -1 1
|
3
|
|
2
|
3 1
-1 -1 1
|
1
|