Description

小田 在一家销售电视机的公司工作。现在，他必须准备一份去年的报告。

小田 有一张公司收入清单。该清单是一个由 $n$ 个整数组成的序列。公司的总收入是序列中所有整数的总和。 为了让报告好看一些，小田 决定对序列中的几个数字进行 $k$ 次符号改变。他可以多次改变一个数字的符号。

改变一个数的符号的操作就是这个数乘以 $-1$ 的操作。

帮助 小田 进行更改，使公司的总收入(结果序列中的数字之和)达到最大值。注意，小田 必须进行 $k$ 次修改。

Input

第一行包含两个整数 $n$ 和 $k$，表示序列中有多少个数字以及要进行多少次交换。 $(1 ≤ n, k ≤ 10^5)$ 第二行包含一个 非递减序列，由 $n$ 个整数 $a_i$ 组成。 $(|a_i| ≤ 10^6)$ .

各行数字之间用单个空格隔开。请注意，给定序列按非递减顺序排序。

Output

在单行中打印出问题的答案，即经过恰好 $k$ 次变化后，我们可以获得的最大总收入。

3 2
-1 -1 1

3 1
-1 -1 1

3

1

Note

第一个测试用例可以修改成 $[1, 1, 1]$ 。 第二个测试用例可以修改成 $[-1, 1, 1]$ 。