解题思路

1. 将问题转化

把每株花对应为一个等长区间，定义覆盖计数 $c(x)$ 为时刻 $x$ 被多少区间覆盖。 我们关心的量为

题目内容

昙花是一种很美丽的花；可惜的是，昙花开花的时间非常短暂，所以才有“昙花一现”之说，人们常说，目睹昙花一现，意味着好的事情即将发生。

小红是一位大魔法师，他种植了 $n$ 株昙花，并预知了这些昙花开花的时间 $t_1,t_2,…,t_n$，每一株昙花只会开花 $m$ 秒，$m$ 是一个固定的数值。也就是说，第 $i$ 株昙花将会在 $[t_i,t_i+m-1]$ 开花。

小红想让自己欣赏昙花开花的时间尽可能长。但是，小红不满足于看两株及以上的昙花开花，他认为那样太过艳丽，有失风采。也就是说，小红想让恰有一株昙花开花的时刻尽可能多。

作为大魔法师，小红可以施展至多一次魔法：他可以选定任意一株昙花，并将这株昙花的开花时间 $t_i$ 修改成任意正整数，请问，小红最多能让恰有一株昙花开花的时间变为多久？

输入描述

本题中，单个测试用例包含多组数据。

第一行一个正整数 $T$ ，表示数据组数。

对于每一组数据：

第一行两个正整数 $n$ 和 $m$

第二行 $n$ 个正整数，表示 $t_1,t_2,...,t_n$ 。

$1≤\sum n≤2*10^5,1≤m,t_i≤5*n,1≤T≤1000$

注意，小红施展魔法时可以将 $t_i$ 修改成任意正整数，不受 $t_i≤5*n$ 的约束。

输出描述

输出 $T$ 行，每行一个非负整数，表示恰有一株昙花开花的最大时刻数。

样例1

输入

2
4 10
1 3 12 20
5 5
2 1 10 3 11

输出

36
12

说明

第一组样例的解释如下：

施展魔法前，四株昙花的开花时间段分别为 $[1,10],[3,12],[12,21]$ 和 $[20,29]$ 。

恰有一株昙花开花的时间段有 $[1,2],[11,11],[13,19]$ 和 $[22,29]$ ，时刻数为 $2+1+7+8=18$ 。

小红可以施展魔法，将 $t_2$ 修改为 $30$ 。

施展魔法后，四株昙花的开花时间段分别为 $[1,10],[30,39],[12,21]$ 和 $[20,29]$ 。

恰有一颗昙花开花的时间段有 $[1,10],[12,19],[22,29]$ 和 $[30,39]$ ，时刻数为 $10+8+10=36$ 。

可以证明没有更优的方案。