题目描述

在平面上有 $N$ 个城市。第 $i$ 个城市位于坐标 $(x_i, y_i)$。可能有多个城市位于同一个坐标。

在坐标 $(a, b)$ 的城市和坐标 $(c, d)$ 的城市之间修建一条道路需要花费 $min(|a-c|, |b-d|)$ 元。只能在城市与城市之间修建道路。

为了使任意两个城市之间都能够通过若干条道路互相到达，至少需要多少元？

输入格式

输入按以下格式从标准输入给出。

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

输出格式

输出为了使任意两个城市之间都能互相到达至少需要花费的最小金额。

样例 1

输入

3
1 5
3 9
7 8

输出

3

样例 2

输入

6
8 3
4 9
12 19
18 1
13 5
7 6

输出

8

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $0 \leq x_i, y_i \leq 10^9$
• 输入均为整数

样例解释 1

在城市 $1$ 和城市 $2$ 之间、城市 $2$ 和城市 $3$ 之间修建道路，则所需金额为 $2 + 1 = 3$ 元。

由 ChatGPT 5 翻译