题目描述

给定n个整数常数$c_1,c_2,...,c_n$和一个整数$k$。现在需要给$2k$个整数变量$x_1,x_2,...,x_k,y_1,y_2,...,y_k$赋值，满足

1. 对于所有 $1 ≤ i ≤ k$，都有$x_i ≤ y_i$。
2. 对于所有 $1 ≤ i ≤ n$，都存在至少一个$j(1 ≤ j ≤ k)$ ，使得$x_j≤c_i≤y_j$。

求出$S=(y_1+y_2+...+y_k)-(x_1+x_2+...+x_k)$ 的最小值。

输入格式

第一行两个整数$n,k$。 接下来一行，共$n$个整数$c_1,c_2,...,c_n$。

输出格式

一个整数表示$S$的最小值。

5 2
-5 0 10 4 0

9

样例输入输出 2

见下发文件。

数据规模

共 10 个测试点。

测试点 1,2 满足$n≤5, − 5 ≤ c_1 ≤ 5$。

测试点 3,4,5 满足$n ≤ 100$。

对于所有数据，满足$1 ≤ n, k ≤ 10^5, −10^9 ≤ c_i ≤ 10^9$。

附件

附件下载