K 社长正在负责调整办公室的室温。他希望尽可能让职员们感到舒适。

现在办公室里有 $N$ 名职员。每名职员的编号为 $1$ 到 $N$，对于职员 $i$ ($1 \le i \le N$)，当他/她不穿外套时，其适宜温度为 $A_i$ 度。对于每名职员，每穿一件外套，其适宜温度就会下降 $T$ 度。换句话说，当职员 $i$ 穿着 $k$ 件外套时，他/她的适宜温度为 $A_i - kT$ 度。

当室温为 $x$ 度，且某位职员的适宜温度为 $y$ 度时，该职员的不适指数表示为 $|x - y|$。注意 $|t|$ 表示 $t$ 的绝对值。每位职员会根据室温，穿着 $0$ 件或更多件外套，以使自己的不适指数最小化。

在此，K 社长将所有职员中的最大不适指数称为“房间的不快度”，并设定室温以使房间的不快度最小化。注意室温必须为整数。

编写一个程序，在给定职员信息和适宜温度的情况下，计算房间的最小不快度。

输入格式

从标准输入读取以下数据：

$N \ T$ $A_1 \ A_2 \ \dots \ A_N$

输出格式

输出一行到标准输出。输出应包含房间的最小不快度。

数据范围

• $2 \le N \le 500\,000$
• $1 \le T \le 10^9$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• 给定值均为整数。

子任务

1. (15 分) $N = 2$
2. (5 分) $N \le 3\,000$，$T = 1$
3. (30 分) $N \le 3\,000$，$T \le 2$
4. (35 分) $N \le 3\,000$，$T \le 3\,000$
5. (15 分) 无附加限制。

样例

样例输入 1

2 4
19 24

样例输出 1

1

说明 1

例如，如果将室温设定为 $16$ 度，职员 $1$ 穿一件外套后的适宜温度为 $15$ 度；不适指数为 $|16 - 15| = 1$。职员 $2$ 穿两件外套后的适宜温度为 $16$ 度；不适指数为 $|16 - 16| = 0$。此时，房间的不快度为 $1$。 由于房间的不快度无法小于 $1$，因此输出 $1$。

样例输入 2

3 1
21 19 23

样例输出 2

0

说明 2

例如，如果将室温设定为 $19$ 度，房间的不快度变为 $0$。输出 $0$。

样例输入 3

6 8
24 22 21 25 29 17

样例输出 3

2

说明 3

例如，如果将室温设定为 $15$ 度，房间的不快度变为 $2$。由于房间的不快度无法小于 $2$，因此输出 $2$。