{"problem":{"name":"D. Monument Tour","description":{"content":"A tour operator proposes itineraries consisting of visits of $N$ monuments and museums in Paris, modeled as a grid. The way the tour operates is the following: The bus enters the city from the west (o","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10246D"},"statements":[{"statement_type":"Markdown","content":"A tour operator proposes itineraries consisting of visits of $N$ monuments and museums in Paris, modeled as a grid. The way the tour operates is the following: The bus enters the city from the west (on any street) and traverses the city, taking a left or a right turn to visit monuments when needed, returning to the same eastbound road it used to enter the city, and so on until it exits the city via the east.\n\nA tour in a $6 times 5$ grid city might look like the figure above. On the figure, the bus enters the city at coordinate $(0, 2)$ (we consider $(0, 0)$ to be the northwest corner of the city), first visits the monument at $(1, 2)$ (already on the main road), takes a left turn and visits the monument at $(1, 0)$, returns to the main road and moves east, takes a right turn and visits the monument at $(2, 4)$, returns to the main road, visits the monument at $(4, 2)$ (again on the main road), and then exits the city at coordinate $(5, 2)$ .\n\nThe bus operator counts that the traversal of one block costs 1 unit of gas. For the example above, the cost is thus $5 + 2 times 2 + 2 times 2 = 13$ units of gas. \n\nYour task is to help the tour operator choose which eastbound road the bus should travel through, so that the cost of the tour is minimized while visiting all $N$ monuments.\n\nThe input comprises several lines, each consisting of integers separated with single spaces: \n\nThe output should consist of a single line, whose content is an integer, representing the minimal cost of a tour.\n\n## Input\n\nThe input comprises several lines, each consisting of integers separated with single spaces:  The first line contains the number $X$ of northbound streets and the number $Y$ of eastbound streets.  The second line contains the number $N$ of monuments the tour needs to visit.  The next N lines each contain the coordinates $x_i$ and $y_i$ of each monument.    $1 <= X, Y <= 100000$;  $1 <= N <= 100000$;  $0 <= x_i < X, quad 0 <= y_i < Y$. \n\n## Output\n\nThe output should consist of a single line, whose content is an integer, representing the minimal cost of a tour.\n\n[samples]\n\n## Note\n\n  The bus operator is not allowed to return to a different, parallel, eastbound road; they have to use the same road as the one by which they entered the city.  More than one monument can be present at the same coordinate.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of monuments.  \nLet $ M = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of monument coordinates, where $ x_i \\in \\mathbb{Z} $ is the east-west position (row) and $ y_i \\in \\mathbb{Z} $ is the north-south position (column).  \nLet $ r \\in \\mathbb{Z} $ be the chosen eastbound road (fixed column) for the bus to traverse.\n\n**Constraints**  \n- The bus enters from the west (left edge) and exits to the east (right edge) along a single horizontal road $ r $.  \n- The bus moves eastward along road $ r $, and makes perpendicular detours (north/south) to visit monuments not on $ r $.  \n- Each monument must be visited exactly once.  \n- The bus must return to road $ r $ after each detour.  \n- All coordinates are within a grid of finite size (implied by input), but absolute bounds are irrelevant for cost computation.\n\n**Objective**  \nMinimize the total gas cost over all possible choices of $ r $:  \n$$\n\\min_{r \\in \\mathbb{Z}} \\left( \\sum_{i=1}^{N} |y_i - r| \\cdot 2 + \\Delta x \\right)\n$$  \nwhere $ \\Delta x $ is the total horizontal distance traveled eastward (from leftmost to rightmost monument’s $ x $-coordinate), and the factor of 2 accounts for round-trip detours (to monument and back to road $ r $).\n\nSince $ \\Delta x $ is independent of $ r $, the objective reduces to:  \n$$\n\\min_{r} \\sum_{i=1}^{N} 2 \\cdot |y_i - r|\n$$  \nThus, the optimal $ r $ is the **median** of the set $ \\{ y_1, y_2, \\dots, y_N \\} $, and the minimal cost is:  \n$$\n2 \\cdot \\sum_{i=1}^{N} |y_i - \\text{median}(\\{y_1, \\dots, y_N\\})| + (\\max_i x_i - \\min_i x_i)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10246D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}