Problem Description

Niwango, an employee of Dwango, loves TV-chan so much that he has collected a large number of TV-chan plushies and arranged them all over the floor.

Niwango has $N$ rare black TV-chan plushies, which he has arranged together with the regular ones. However, it is difficult to manage them when they are scattered everywhere, so he decided to gather them close together.

There are plushies placed on every lattice point of an infinitely large two-dimensional plane. The coordinates $(x_i, y_i)$ of the $N$ black plushies are given. The plushies are treated as points.

Niwango can perform the following operation any number of times:

• Place a square with sides parallel to the axes and a side length of $D$ such that each vertex coincides with a lattice point, and rotate the $4$ points at the corners of the square by $90$ degrees together with the $4$ plushies there. That is, if the bottom-left vertex of the square is $(x, y)$, the points $(x, y) \rightarrow (x+D, y) \rightarrow (x+D, y+D) \rightarrow (x, y+D) \rightarrow (x, y)$ are rotated simultaneously.

The messiness of the arrangement is defined as the minimum side length of a square with sides parallel to the axes needed to enclose all the black plushies. Here, plushies on the edges of the square are considered to be enclosed.

Find the minimum possible value of the messiness after Niwango performs the operations several times.

Input Format

The input is given from the standard input in the following format:

$N$ $D$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 1
0 0
1 0
2 0

Sample Output #1

1

Sample Input #2

19 2
1 3
2 3
0 1
1 1
2 1
3 1
4 4
5 4
6 4
7 4
8 4
8 3
8 2
8 1
8 0
7 0
6 0
5 0
4 0

Sample Output #2

4

Sample Input #3

8 3
0 0
0 3
3 0
3 3
2 2
2 5
5 2
5 5

Sample Output #3

4

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq D \leq 1000$
• $0 \leq x_i, y_i \leq 10^9$
• All given coordinates are distinct
• All numbers given in the input are integers

Partial Points

• Correctly solving the dataset where $1 \leq D \leq 30$ will award $500$ points.

见题面 Input 部分

见题面 Output 部分