CF2025C New Game

Monocarp 想玩一个新游戏。这个游戏使用一副有 $n$ 张牌的牌堆，第 $i$ 张牌上写着一个整数 $a_i$。 游戏开始时，在第一回合，Monocarp 可以从牌堆中拿走任意一张牌。在之后的每一回合，Monocarp 只能拿走一张牌，这张牌上写的数字要么与上一回合拿走的牌上的数字相同，要么比上一回合拿走的牌上的数字大 $1$。 换句话说，如果上一回合 Monocarp 拿走的牌上的数字是 $x$，那么这一回合他可以拿走数字为 $x$ 或 $x+1$ 的任意一张牌，无论它在牌堆中的位置如何。 每当 Monocarp 拿走一张牌，这张牌就会从牌堆中移除。 根据游戏规则，Monocarp 拿走的牌上所写的不同数字的数量不能超过 $k$。 如果在某一回合后，Monocarp 无法在不违反上述规则的情况下继续拿牌，游戏就结束。 你的任务是：给定初始牌堆，求 Monocarp 在游戏中最多能拿走多少张牌。第一回合可以拿任意一张牌。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 200\,000$），分别表示牌堆中的牌数和 Monocarp 能拿的牌上不同数字的最大数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{9}$），表示每张牌上的数字。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $200\,000$。

对于每个测试用例，输出一行，表示 Monocarp 在游戏中最多能拿走的牌数。

在第一个样例中，Monocarp 需要先拿任意一张数字为 $3$ 的牌。接下来的两回合，他需要拿剩下的两张数字为 $3$ 的牌。再接下来的三回合，他需要拿三张数字为 $4$ 的牌。之后，Monocarp 将无法再拿牌，此时他一共拿了 $6$ 张牌。 由 ChatGPT 4.1 翻译