Problem Description

Given a sequence of $n$ natural numbers $x_1, x_2, ..., x_n$.

Now, assign either a positive sign ($+x_i$) or a negative sign ($-x_i$) to each number $x_i$ in the sequence, and then compute the sum.

Specifically, among the $n$ numbers, exactly $k$ numbers must use the positive sign, and the remaining $n-k$ numbers must use the negative sign.

Determine the maximum possible sum that can be obtained through this operation.

Input Format

The first line contains two integers $n$ and $k$, representing the length of the sequence and the required number of positive signs, respectively.

The second line contains $n$ natural numbers $x_1, x_2, ..., x_n$, representing the given sequence. It is guaranteed that $x_1 \ge x_2 \ge ... \ge x_n$.

Output Format

A single line containing an integer, representing the maximum possible sum that can be obtained.

3 2
5 2 1

6

Hint

[Constraints]

For $20\%$ of the data, $1 \le n \le 10$.

For another $10\%$ of the data, $n = k$.

For another $10\%$ of the data, all $x_i$ are equal.

For $100\%$ of the data, $1 \le k \le n \le 10^5$, $0 \le x_i \le 10^9$.

Translated by DeepSeek-V3