{"problem":{"name":"Rooks","description":{"content":"You are given positions $(X_i, Y_i)$ of $N$ enemy rooks on an infinite chessboard. No two rooks attack each other (at most one rook per row or column). You're going to replace one rook with a king and","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":1250,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc047_f"},"statements":[{"statement_type":"Markdown","content":"You are given positions $(X_i, Y_i)$ of $N$ enemy rooks on an infinite chessboard. No two rooks attack each other (at most one rook per row or column).\nYou're going to replace one rook with a king and then move the king repeatedly to beat as many rooks as possible.\nYou can't enter a cell that is being attacked by a rook. Additionally, you **can't move diagonally to an empty cell** (but you can beat a rook diagonally).\n(So this king moves like a superpawn that beats diagonally in 4 directions and moves horizontally/vertically in 4 directions.)\nFor each rook, consider replacing it with a king, and find the minimum possible number of moves needed to beat the maximum possible number of rooks.\n\n## Constraints\n\n*   $2 \\leq N \\leq 200\\,000$\n*   $1 \\leq X_i, Y_i \\leq 10^6$\n*   $X_i \\neq X_j$\n*   $Y_i \\neq Y_j$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format.\n\n$N$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$\\vdots$\n$X_N$ $Y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc047_f","tags":[],"sample_group":[["6\n1 8\n6 10\n2 7\n4 4\n9 3\n5 1","5\n0\n7\n5\n0\n0\n\nSee the drawing below. If we replace rook 3 with a king, we can beat at most two other rooks. The red path is one of optimal sequences of moves: beat rook 1, then keep going down and right until you can beat rook 4. There are 7 steps and that's the third number in the output.\n![image](https://img.atcoder.jp/agc047/rooks_path_small3.png)\n_x-coordinate increases from left to right, while y increases bottom to top._\nStarting from rook 2, 5 or 6, we can't beat any other rook. The optimal number of moves is 0."],["5\n5 5\n100 100\n70 20\n81 70\n800 1","985\n985\n1065\n1034\n0"],["10\n2 5\n4 4\n13 12\n12 13\n14 17\n17 19\n22 22\n16 18\n19 27\n25 26","2\n2\n9\n9\n3\n3\n24\n5\n0\n25"]],"created_at":"2026-03-03 11:01:14"}}