2024-ho-t1_Room_Temperature — JOI JOI
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 14
Algorithms: greedy, sorting

![](_page_0_Picture_0.jpeg)

# 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 officer *i* (1 ≤ *i* ≤ *N*) is *A<sub>i</sub>* 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<sub>i</sub>* − *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.

### Input

Read the following data from the standard input.

*N T*
*A<sub>1</sub> A<sub>2</sub> ... A<sub>N</sub>*

### Output

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

![](_page_1_Picture_0.jpeg)

### Constraints

*   2 ≤ *N* ≤ 500 000.
*   1 ≤ *T* ≤ 10<sup>9</sup>.
*   1 ≤ *A<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   Given values are all integers.

### Subtasks

1.  (15 points) *N* = 2.
2.  (5 points) *N* ≤ 3 000, *T* = 1.
3.  (30 points) *N* ≤ 3 000, *T* ≤ 2.
4.  (35 points) *N* ≤ 3 000, *T* ≤ 3 000.
5.  (15 points) No additional constraints.

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| 2 4            | 1              |
| 19 24          |                |

For example, if the room temperature is set to 16 degrees, the appropriate temperature for officer 1 will be 15 degrees by wearing one jacket; the discomfort index is |16 − 15| = 1. The appropriate temperature for officer 2 will be 16 degrees by wearing two jackets; the discomfort index is |16 − 16| = 0. At this time, the room's unpleasantness becomes 1.

Since the room's unpleasantness cannot be made smaller than 1, output 1.

This sample input satisfies the constraints of Subtasks 1, 4, 5.

![](_page_2_Picture_0.jpeg)

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| 3 1            | 0              |
| 21 19 23       |                |

For example, if the room temperature is set to 19 degrees, the room's unpleasantness becomes 0. Output 0. This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.

| Sample Input 3    | Sample Output 3 |
| :------------- | :------------- |
| 6 8               | 2              |
| 24 22 21 25 29 17 |                |

For example, if the room temperature is set to 15 degrees, the room's unpleasantness becomes 2. Since the room's unpleasantness cannot be made smaller than 2, output 2.

This sample input satisfies the constraints of Subtasks 4, 5.

Starter code: