B4468 Symbol Selection / opt

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.

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$.

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

#### [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