贸易

时间限制： 1 秒
内存限制： 256 MB
输入： 标准输入
输出： 标准输出

题目描述

市场和贸易是文明的重要方面。任何足够熟练的《文明》玩家在某个时刻都会达到游戏的一个阶段，此时他的仓库堆满了各种各样的稀有资源。有时它们变得如此之多，以至于计算每种资源的最佳售价变得不可能。

帕夏也遇到了同样的情况。为了简化游戏的剩余部分，他决定提高一些稀有资源的价格，使得其中恰好有 $k$ 种不同的价格，并且总价格涨幅最小。

更形式化地说，目前他的文明销售 $n$ 种商品，每种商品有自己的价格 $s_i$，并且所有 $s_i$ 互不相同。需要为商品选择新的价格 $e_i$，使得：

• 所有 $e_i$ 是整数；
• 对于所有 $i$，有 $e_i \ge s_i$；
• 在所有 $e_i$ 中，恰好有 $k$ 个不同的数值（不多不少）；
• $\sum\limits_{i=1}^n (e_i - s_i)$ 最小。

你需要找到这样一组价格，并确定对应的所有商品总价格涨幅。

输入数据

每个测试包含多个测试用例。第一行包含一个整数 $t$ —— 测试用例的数量 ($1 \le t \le 10^3$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ —— 商品数量和所需的不同价格数量，分别 ($1 \leq k \leq n \leq 2 \cdot 10^3$)。

第二行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$ —— 商品价格 ($1 \leq s_i \leq 10^9$；所有 $s_i$ 互不相同)。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^3$。

输出数据

对于每个测试用例，在一行中输出一个整数 —— 满足所有要求的最小总价格上涨。

评分系统

仅当子任务的所有测试及其必需的子任务全部通过时，该子任务的分数才会被计算。令 $N$ 表示所有测试用例的 $n$ 之和。

示例

输入

3
4 2
1 2 4 3
7 3
1 5 12 4 11 6 3
9 5
4 6 13 1 3 8 7 12 5

输出

2
6
4