题目描述

Alice 的曲库一共有 $n$ 张谱面，第 $i$ 张谱面有一个整数难度值 $a_i$ Alice 初始时能力值为一个整数 $m$ ，还有一个难度阈值 $d$ ，后面会介绍 $d$ 的用处。

Alice 可以以任意顺序游玩这些谱面，但是每个谱面只能游玩一次。

如果 Alice 当前的能力值为 $x$ ，游玩第 $i$ 张谱面时：

如果 $a_i \lt x-d$ ，这个谱面对于 Alice 来说过于简单，他的能力值不会改变。

如果 $x-d \le a_i \le x$ ，他的能力值会增加 $1$ 。

如果 $x \lt a_i \le x+d$ ，适当的越级打歌，他的能力值会增加 $2$ 。

如果 $x+d \lt a_i$ ，这张谱面对于 Alice 来说过难了，乱糊不会增加能力值。

Alice 想知道如果他最终能力值可能达到的最大值是多少。

输入格式

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

对于每组数据：

第一行三个整数 $n,m,d$ 分别表示谱面的数量， Alice 初始能力值，难度阈值。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$ 为 $n$ 个谱面的难度。

输出格式

对于每组数据，输出一行一个整数表示 Alice 能达到的最大能力值。

样例 #1

样例输入 #1

5
7 2 1
2 6 11 4 14 15 15 
7 3 2
2 5 6 12 2 7 10 
6 0 1
-4 1 -1 -3 1 -3 
5 -3 1
-4 -1 -1 3 1 
7 0 0
-7 -5 -5 0 -3 0 -5

样例输出 #1

7
13
3
4
1

样例 #2

样例输入 #2

7
10 2 1
-6 2 3 -3 -6 5 2 8 0 7 
6 3 0
-2 3 3 3 3 3 
6 -11 1
-13 -10 -10 -10 -12 -13 
5 0 1
0 8 11 6 3 
13 0 3
-8 5 -5 6 9 -8 -6 2 1 11 -6 -2 -3 
6 5 1
4 9 5 8 14 11 
8 -1 2
-5 1 -4 1 3 5 1 1

样例输出 #2

9
4
-8
1
11
12
6

样例 #3

见附加文件中的 sample3.in/sample3.out.

附加文件下载

提示

对于 $20\%$ 的数据，$T \le 100,n \le 8$ 。

对于另外 $20\%$ 的数据，$d \le 1$ 。

对于另外 $30\%$ 的数据，$\sum{n} \le 10^3$ 。

对于全部数据，$1 \le n \le 10^5, \sum{n} \le 5 \times 10^5 , -10^9 \le a_i,m \le 10^9 , 0\le d \le 10^5,\sum{d} \le 5 \times 10^5$。

$\sum{n}$ 为 $T$ 组数据中 $n$ 的总和，$\sum{d}$ 为 $T$ 组数据中 $d$ 的总和。