31623번 - Room Temperature 서브태스크다국어

President K is taking on the role of adjusting the room temperature of the officers’ room. He wants to make the officers as comfortable as possible.

Now there are $N$ officers in the room. Each officer is numbered from $1$ to $N$, and the appropriate temperature for officers $i$ ($1 ≤ i ≤ N$) is $A_i$ degrees when (s)he is not wearing jackets. For each officer, the appropriate temperature drops by $T$ degrees every time (s)he wears a jacket. In other words, when the officer $i$ is wearing $k$ jackets, her/his appropriate temperature is $A_i − kT$ degrees.

When the room temperature is $x$ degrees and the appropriate temperature of a certain officer is $y$ degrees, the discomfort index of the officer is expressed as $|x − y|$. Note that $|t|$ represents the absolute value of $t$. Each officer wears the appropriate number of jackets of $0$ or more to minimize discomfort index, depending on the room temperature.

Here, president K decided to call the maximum discomfort index among all officers as room’s unpleasantness, and set the room temperature so that the room’s unpleasantness was minimized. Note that the room temperature must be an integer.

Write a program which, given information about the officers and the appropriate temperature, calculates the minimum room’s unpleasantness.

Read the following data from the standard input.

$N$ $T$

$A_1$ $A_2$ $\cdots$ $A_N$

Write one line to the standard output. The output should contain the minimum room’s unpleasantness.

• $2 ≤ N ≤ 500\, 000$.
• $1 ≤ T ≤ 10^9$.
• $1 ≤ A_i ≤ 10^9$ ($1 ≤ i ≤ N$).
• Given values are all integers.