题目描述

给定一个包含 n 个自然数的序列 x₁, x₂, ..., xₙ。
现在要对序列中的每个数 xᵢ 赋予一个正号 (+xᵢ) 或负号 (-xᵢ)，然后求和。
特别的，在 n 个数中，必须恰好有 k 个数使用正号，其余 n-k 个数使用负号。
求这种操作下，得到的最大总和是多少。

输入格式

从文件 opt.in 中读入数据。
第一行包含两个整数 n 和 k，分别表示序列的长度和必须选择加号的次数。
第二行包含 n 个自然数 x₁, x₂, ..., xₙ，表示给定的序列，保证 x₁ ≥ x₂ ≥ ... ≥ xₙ。

输出格式

输出到文件 opt.out 中。
一行，包含一个整数，表示能够得到的最大总和。

3 2
5 2 1

6

数据范围

• 对于 20% 的数据，1 ≤ n ≤ 10。
• 对于另外 10% 的数据，n = k。
• 对于另外 10% 的数据，每个 xᵢ 相等。
• 对于 100% 的数据，1 ≤ k ≤ n ≤ 10⁵，0 ≤ xᵢ ≤ 10⁹。

题目来源

2025 山西省小学生编程未来星启航计划