{"problem":{"name":"Square Rotation","description":{"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. Niwango-kun has $N$ black rare soft toys of Niconico TV-ch","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2525,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dwacon5th_prelims_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $D$\n$x_1$ $y_1$\n$:$\n$x_N$ $y_N$\n\n## Partial Scores\n\n*   $500$ points will be awarded for passing the test set satisfying $1 \\leq D \\leq 30$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dwacon5th_prelims_d","tags":[],"sample_group":[["3 1\n0 0\n1 0\n2 0","1"],["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","4"],["8 3\n0 0\n0 3\n3 0\n3 3\n2 2\n2 5\n5 2\n5 5","4"]],"created_at":"2026-03-03 11:01:14"}}