/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
Score: 100 points
Problem Statement
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
Xto the end of S. This operation costs 1. - Operation 2: Increase the robot's y coordinate by 1 and append
Yto 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
Output
Output the minimum cost required for the robot to visit all points in order.
Sample Input 1
2 3 3 1 2
Sample 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.
Sample Input 2
3 2 2 3 3 1 3
Sample Output 2
7
配点 : 100 点
問題文
xy 平面上に 1, 2, \dots, N の番号が付けられた N 個の点があります。点 i (1 \le i \le N) の座標は (X_i, Y_i) です。
この平面上の原点にロボットがあります。あなたはこのロボットを操縦して、点 1, 2, \dots, N を この順にすべて 訪れなければなりません。
ロボットは文字列変数 S を持っています。はじめ、S は空文字列です。
あなたは以下の 4 種類の操作でロボットを動かすことができます。
- 操作 1 : ロボットの x 座標を 1 増やし、S の末尾に
Xを追加する。この操作には 1 のコストがかかる。 - 操作 2 : ロボットの y 座標を 1 増やし、S の末尾に
Yを追加する。この操作には 1 のコストがかかる。 - 操作 3 : ロボットの x 座標を 1 減らし、S の末尾の文字を削除する。この操作は S の末尾の文字が
Xであるときのみ行える。この操作にコストはかからない。 - 操作 4 : ロボットの y 座標を 1 減らし、S の末尾の文字を削除する。この操作は S の末尾の文字が
Yであるときのみ行える。この操作にコストはかからない。
点 1, 2, \dots, N をこの順に訪れるのにかかるコストの最小値を求めてください。
制約
- 入力はすべて整数
- 1 \le N \le 500
- 0 \le X_i, Y_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
ロボットが点 1, 2, \dots, N をこの順に訪れるのにかかるコストの最小値を出力せよ。
入力例 1
2 3 3 1 2
出力例 1
6
操作 1 を 1 回、操作 2 を 3 回、操作 1 を 2 回することで、点 1 を訪れることができ、 続けて、操作 3 を 2 回、操作 4 を 1 回することで、点 2 を訪れることができます。
上記の一連の操作のコストは、操作 1, 2 を行った回数の合計である 6 になります。
入力例 2
3 2 2 3 3 1 3
出力例 2
7