K 理事长负责调节有高管在的房间温度，他希望让高管们尽可能地舒适。

现在，房间里有 $N$ 名高管。每位高管都有从 $1$ 到 $N$ 的编号，高管 $i$（$1 \leq i \leq N$）脱掉外套时的适宜温度为 $A_i$ 度。此外，每穿一件外套，他的适宜温度就会降低 $T$ 度。也就是说，高管 $i$ 穿 $k$ 件外套时，他的适宜温度为 $A_i-kT$ 度。

如果房间温度为 $x$ 度，某位高管的适宜温度为 $y$ 度，则该高管的不适感为 $|x-y|$，其中 $|t|$ 表示 $t$ 的绝对值。每位高管会根据房间温度选择穿合适的外套数量（可以为 $0$ 件或更多），以使自己不适感最小。

此时，K 理事长将所有高管不适感的最大值称为“房间的不适感”，并希望通过设置房间温度，使得房间的不适感最小。房间温度必须为整数。

请你编写一个程序，根据高管和适宜温度的信息，求出房间不适感可能取得的最小值。

输入通过标准输入给出，格式如下：

$N\ T\ A_1\ A_2\ \cdots\ A_N$

请输出房间不适感的最小可能值，输出一行。

小子任务

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

样例说明 1

例如，如果房间温度设置为 $16$ 度，高管 $1$ 穿 $1$ 件外套，适宜温度变为 $15$ 度，高管 $1$ 的不适感为 $|16-15|=1$。高管 $2$ 穿 $2$ 件外套，适宜温度变为 $16$ 度，不适感为 $|16-16|=0$。

此时，房间不适感为 $1$。且不能让房间不适感小于 $1$，所以输出 $1$。

该输入例满足小子任务 $1,4,5$ 的限制。

样例说明 2

例如，将房间温度设置为 $19$ 度，房间的不适感为 $0$。因此输出 $0$。

该输入例满足小子任务 $2,3,4,5$ 的限制。

样例说明 3

例如，将房间温度设置为 $15$ 度，房间的不适感为 $2$。不能让房间不适感小于 $2$，因此输出 $2$。

该输入例满足小子任务 $4,5$ 的限制。

数据范围与约定

• $2 \leq N \leq 500\,000$。
• $1 \leq T \leq 10^9$。
• $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。
• 输入数据均为整数。

由 ChatGPT 5 翻译