AT_ttpc2024_1_e ReTravel

$ 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 $ をこの順に訪れるのにかかるコストの最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

ロボットが点 $ 1, 2, \dots, N $ をこの順に訪れるのにかかるコストの最小値を出力せよ。

### Sample Explanation 1 操作 $ 1 $ を $ 1 $ 回、操作 $ 2 $ を $ 3 $ 回、操作 $ 1 $ を $ 2 $ 回することで、点 $ 1 $ を訪れることができ、 続けて、操作 $ 3 $ を $ 2 $ 回、操作 $ 4 $ を $ 1 $ 回することで、点 $ 2 $ を訪れることができます。 上記の一連の操作のコストは、操作 $ 1, 2 $ を行った回数の合計である $ 6 $ になります。 ### Constraints - 入力はすべて整数 - $ 1 \le N \le 500 $ - $ 0 \le X_i, Y_i \le 10^9 $