← 返回题目列表

Codeforces · 262/B

B. 罗姆人和不断变化的标志

中文机器翻译题面 查看原题

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。