Migrated from Lutece 3187 阻止悲剧

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

「先从我眼前消失的是你吧！？」

「擅自跑到我无法触及的地方去的人是你吧！」

「明明遥不可及，却又近在咫尺，先想出这种拷问方式的人是你吧！」

「明明是这样，为什么还非得被你责备不可啊……？」

「像那样……每天、每天，在我的眼前，剐着我的心……」

「还说这全都是我的错……太残忍了啊……」

---

$$$$

你下定决心要解决这场悲剧，解决这场悲剧的方法也很简单——让北原春希单身：你需要传送到每个女主的好感度上升事件的时间点，并阻止该事件的发生。

你需要阻止的时间点有 $n$ 个，它们很奇怪，位于一个二维平面上，各自可以用 $(x_i, y_i)$ 来表示其位置。你可以选择任意一个时间点作为起始点，并遵从该平面中时间流动的法则——你只能从一个纵坐标相对大的时间点到达一个没有到达过的纵坐标相对小的时间点，代价为两个点间的曼哈顿距离。

但显然这并不一定能遍历完所有的时间点，但是你拥有一项特殊能力，对于每个你曾经到达过的点，你都能够回去一次且仅一次，代价为 $0$。

换句话说：在一个时间点 $u$，你有两种操作：第一种操作是是前往一个点 $v$，点 $v$ 满足 $y_v < y_u$ 且没有到达过，代价为 $|x_u - x_v| + |y_u - y_v|$；另一种是前往一个点 $w$，点 $w$ 满足曾经到达过但没有通过第二种操作到达过的点，代价为 $0$。

现在你能自选一个点作为出发点，请问到达所有时间点的最小代价是多少？

如果不管怎样，都不能到达所有时间点，则输出 $-1$。

Input

第一行一个正整数 $n$，代表时间点的数量。

接下来 $n$ 行，每行两个数字 $x_i$, $y_i$，分别代表一个时间点的横纵坐标。

Output

如果有方案能遍历所有时间点，则输出一个非负数，代表遍历完所有时间点的最小代价。

否则，输出 $-1$。

Samples

3
0 0
1 0
2 1

5

4
0 0
1 0
2 1
2 0

-1

5
0 2
-1 1
1 1
-1 0
0 0

7

Constraints

$2 \le n \le 400$

$0 \le |x_i|, |y_i| \le 10^9$

Note

对于第三组样例（箭头上第一个数字代表操作类型，第二个数字代表该操作代价）：

$$(0, 2) \xrightarrow{1, 2} (-1, 1) \xrightarrow{1, 1} (-1, 0) \xrightarrow{2, 0} (-1, 1) \xrightarrow{1, 2} (0, 0) \xrightarrow{2, 0} (0, 2) \xrightarrow{1, 2} (1, 1) $$

神中神：

恋色空

After All〜綴る想い〜

届かない恋

Resources

2024 UESTC ICPC Training for Graph