Roma 在一家销售电视的公司工作。现在他必须准备一份去年的报告。
Roma 已获得公司收入清单。该列表是由 n 个整数组成的序列。公司的总收入是所有整数按顺序排列的总和。 Roma 决定对序列中的几个数字的符号进行恰好 k 次更改。他还可以改变数字的符号一、两次或更多次。
改变一个数的符号的操作就是将该数乘以-1的操作。
帮助 Roma 执行更改,以使公司的总收入(结果序列中的数字之和)最大。请注意,Roma 应该恰好执行 k 个更改。
输入
第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 105),显示序列中有多少个数字以及要进行多少次交换。
第二行包含一个非递减序列,由 n 个整数 ai (|ai| ≤ 104) 组成。
行中的数字由单个空格分隔。请注意,给定的序列按非降序排序。
输出
在一行中打印出问题的答案——恰好 k 个变化后我们可以获得的最大总收入。
示例
输入 #1
3 2 -1 -1 1
输出 #1
3
输入 #2
3 1 -1 -1 1
输出 #2
1
注意
在第一个样本中,我们可以得到序列 [1, 1, 1],因此总收入等于 3。
在第二次测试中,最优策略是得到序列 [-1, 1, 1],因此总收入等于 1。