题目描述

输入格式

输出格式

For each test, output one line containing a single integer-the minimal cost

题目大意

K-Anonymous 序列

题目描述

各种应用领域中爆炸式增长的网络数据引发了相关个人的隐私问题。最近的研究表明，在发布图形/社交网络数据之前简单地删除节点的身份并不能保证隐私。图本身的结构及其基本形式——节点度，可以揭示个体的身份。
为了解决这个问题，我们研究了一个特定的图匿名化问题。我们称一个图为$k-anonymous$，如果对于每个节点$v$，图中至少存在$k-l$个与$v$具有相同程度的其他节点。我们感兴趣的是在具有最少图修改操作的图上实现$k-anonymous$。
我们简化了这个问题。从整个图$G$中选取$n$个节点，并按升序列出它们的度数。我们定义一个序列$k-anonymous$，如果对于每个元素$s$，序列中至少存在$k-1$个等于$s$的其他元素。要让给定的序列$k-anonymous$，你只能做一个操作——减少序列中的一些数字。我们定义了修改的成本，即你修改的所有数字的差值。例如，$k=3$的序列$2,2,3,4,4,5,5$可以修改为$2,2,2,4,4,4,4,4$，满足$3-anonymous$，修改的成本为$|3-2|+|5-4|+|5-4|=3$。
给出一个按升序排列的数字和$k$的序列，我们想知道在所有调整欧速序列$k-anonymous$的修改中，成本最小的修改。

输入格式

输入文件的第一行包含一个整数$T$$（1≤T≤20）$——输入文件中的测试数。每个测试都从包含两个数字$n$$（2≤n≤50000）$的行开始——序列中的数字数量和$k$$（2≤k≤n）$。它后面是$n$个整数的一行，即按升序排列的度数序列。序列中的每个数字$s$都在$[0,5000000]$范围内。

输出格式

对于每个测试，输出一行包含一个整数——最小成本。

翻译提供者：csyc5586

2
7 3
2 2 3 4 4 5 5
6 2
0 3 3 4 8 9

3
5