题目描述

给出一个长度为 $n$ 的非严格递增整数序列，每次操作可以将其中的一个数减少一，问最少多少次操作后能够使得序列中的任何一个数在序列中都至少有 $k$−1 个数与之相同。

输入格式

第一行包含整数 $T$，表示共有$T$组测试数据。

每组测试数据，第一行包含两个整数 $n$ 和$k$。

第二行包含 $n$个不超过 500,000 的非负整数，表示完整的整数序列。

输出格式

每组测试数据输出一个整数，表示所需最少操作数。

每个结果占一行。

样例

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

3
5

数据范围

$1≤T≤20, 2≤n≤500000, 2≤k≤n$

来源

• POJ3709
• 算法竞赛进阶指南