ReTravel

AtCoder

IDttpc2024_1_e

Time2000ms

Memory256MB

Difficulty—

On the $xy$\-plane, there are $N$ points labeled $1, 2, \dots, N$. The coordinates of point $i$ ($1 \le i \le N$) are $(X_i, Y_i)$. There is a robot at the origin of this plane. Your task is to control the robot to visit all the points $1, 2, \dots, N$ **in this order**. The robot has a string variable $S$, which is initially an empty string. You can move the robot using the following four types of operations: * Operation $1$: Increase the robot's $x$ coordinate by $1$ and append `X` to the end of $S$. This operation costs $1$. * Operation $2$: Increase the robot's $y$ coordinate by $1$ and append `Y` to the end of $S$. This operation costs $1$. * Operation $3$: Decrease the robot's $x$ coordinate by $1$ and remove the last character of $S$. This operation can only be performed if the last character of $S$ is `X`. This operation costs $0$. * Operation $4$: Decrease the robot's $y$ coordinate by $1$ and remove the last character of $S$. This operation can only be performed if the last character of $S$ is `Y`. This operation costs $0$. Find the minimum cost required for the robot to visit all points $1, 2, \dots, N$ in this order. ## Constraints * All input values are integers. * $1 \le N \le 500$ * $0 \le X_i, Y_i \le 10^9$ ## Input The input is given from Standard Input in the following format: $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$ [samples]

Samples

Input #1

2
3 3
1 2

Output #1

6

By performing Operation $1$ once, Operation $2$ three times, and Operation $1$ twice, you can reach point $1$.  
Then, by performing Operation $3$ twice and Operation $4$ once, you can reach point $2$.
The total cost of this sequence of operations is the sum of the number of times Operations $1$ and $2$ are performed, which is $6$.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "ReTravel",
    "description": {
      "content": "On the $xy$\\-plane, there are $N$ points labeled $1, 2, \\dots, N$. The coordinates of point $i$ ($1 \\le i \\le N$) are $(X_i, Y_i)$. There is a robot at the origin of this plane. Your task is to contro",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "ttpc2024_1_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On the $xy$\\-plane, there are $N$ points labeled $1, 2, \\dots, N$. The coordinates of point $i$ ($1 \\le i \\le N$) are $(X_i, Y_i)$.\nThere is a robot at the origin of this plane. Your task is to contro...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments