{"trustable":false,"sections":[{"title":"Problem Statement","value":{"format":"HTML","content":" \u003cp\u003eSnuke is the owner of $N$ airports. The coordinates of the $i$-th airport are $(x_i\n, y_i)$. Snuke chooses\na constant $D$, and for each pair of two airports $p$ and $q$, adds a flight between these two airports\nif the Manhattan distance between $p$ and $q$ is at least $D$. Compute the maximum $D$ that makes\nthe airports connected (that is, any airport is reachable from any other airport by using one or\nmore flights).\n\u003c/p\u003e\n\u003cp\u003e\nNote that the Manhattan distance between two points with coordinates $(x_1, y_1)$ and $(x_2, y_2)$ is\ndefined as $|x_1 − x_2| + |y_1 − y_2|$.\n\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"First line of the input contains one integer $N (2 \\leq N \\leq 10^5)$. Then $N$ lines follow, $i$-th of them contains two integers $x_i$ and $y_i$ — coordinates of the $i$-th airport $(0 \\leq x_i\n, y_i \\leq 10^9)$. No two airports share the same position."}},{"title":"Output","value":{"format":"HTML","content":"Print the answer to the problem in a single line."}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\n1 7\n8 5\n6 3\n10 3\n5 2\n6 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\u003csection\u003e\n\n\u003c/section\u003e"}}]}