题目描述

给定一个包含 $n$ 个自然数的序列 $x_1, x_2, \dots, x_n$。

现在要对序列中的每个数 $x_i$ 赋予一个正号 $(+x_i)$ 或负号 $(-x_i)$，然后求和。

特别的，在 $n$ 个数中，必须恰好有 $k$ 个数使用正号，其余 $n-k$ 个数使用负号。

求这种操作下，得到的最大总和是多少。

输入格式

从文件 $\textit{\textbf{opt.in}}$ 中读入数据。

第一行包含两个整数 $n$ 和 $k$，分别表示序列的长度和必须选择加号的次数。 第二行包含 $n$ 个自然数 $x_1, x_2, \dots, x_n$，表示给定的序列，保证 $x_1 \ge x_2 \ge \dots \ge x_n$。

输出格式

输出到文件 $\textit{\textbf{opt.out}}$ 中。

一行，包含一个整数，表示能够得到的最大总和。

样例

3 2
5 2 1

6

数据范围

• 对于 $20\%$ 的数据，$1 \le n \le 10$。
• 对于另外 $10\%$ 的数据，$n = k$。
• 对于另外 $10\%$ 的数据，每个 $x_i$ 相等。
• 对于 $100\%$ 的数据，$1 \le k \le n \le 10^5$，$0 \le x_i \le 10^9$。