{"raw_statement":[{"iden":"problem statement","content":"Niwango-kun, an employee of Dwango Co., Ltd., likes Niconico TV-chan, so he collected a lot of soft toys of her and spread them on the floor.\nNiwango-kun has $N$ black rare soft toys of Niconico TV-chan and they are spread together with ordinary ones. He wanted these black rare soft toys to be close together, so he decided to rearrange them.\nIn an infinitely large two-dimensional plane, every lattice point has a soft toy on it. The coordinates $(x_i,y_i)$ of $N$ black rare soft toys are given. All soft toys are considered to be points (without a length, area, or volume).\nHe may perform the following operation arbitrarily many times:\n\n*   Put an axis-aligned square with side length $D$, rotate the square by $90$ degrees with four soft toys on the four corners of the square. More specifically, if the left bottom corner's coordinate is $(x, y)$, rotate four points $(x,y) \\rightarrow (x+D,y) \\rightarrow (x+D,y+D) \\rightarrow (x,y+D) \\rightarrow (x,y)$ in this order. Each of the four corners of the square must be on a lattice point.\n\nLet's define the _scatteredness_ of an arrangement by the minimum side length of an axis-aligned square enclosing all black rare soft toys. Black rare soft toys on the edges or the vertices of a square are considered to be enclosed by the square.\nFind the minimum scatteredness after he performs arbitrarily many operations."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq D \\leq 1000$\n*   $0 \\leq x_i, y_i \\leq 10^9$\n*   Given coordinates are pairwise distinct\n*   All numbers given in input are integers"},{"iden":"partial scores","content":"*   $500$ points will be awarded for passing the test set satisfying $1 \\leq D \\leq 30$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $D$\n$x_1$ $y_1$\n$:$\n$x_N$ $y_N$"},{"iden":"sample input 1","content":"3 1\n0 0\n1 0\n2 0"},{"iden":"sample output 1","content":"1"},{"iden":"sample input 2","content":"19 2\n1 3\n2 3\n0 1\n1 1\n2 1\n3 1\n4 4\n5 4\n6 4\n7 4\n8 4\n8 3\n8 2\n8 1\n8 0\n7 0\n6 0\n5 0\n4 0"},{"iden":"sample output 2","content":"4"},{"iden":"sample input 3","content":"8 3\n0 0\n0 3\n3 0\n3 3\n2 2\n2 5\n5 2\n5 5"},{"iden":"sample output 3","content":"4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}