AT_joi2024ho_a 室温 (Room Temperature)

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 翻译