← 返回题目列表

AtCoder · arc076_b

D. 建好了吗?

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 飞机上的城镇。的 i第-个城镇位于坐标处 (x_i,y_i)。同一坐标处可能有多个城镇。

您可以在坐标处的两个城镇之间修建一条道路 (a,b) 和 (c,d) 费用为 min(|a-c|,|b-d|) 日元(日本的货币)。不可能修建其他类型的道路。

你的目标是修建道路,以便可以通过道路在每对城镇之间旅行。至少需要多少钱才能实现这个目标?

约束

  • 2 ≤ N ≤ 10^5
  • 0 ≤ x_i,y_i ≤ 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
:
x_N y_N

输出

打印修建道路所需的最低金额,以便可以通过道路在每对城镇之间行驶。


示例输入 1

3
1 5
3 9
7 8

示例输出 1

3

在城镇之间修建道路 1 和 2,以及城镇之间的另一个 2 和 3。总成本是 2+1=3 日元。


示例输入 2

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

示例输出 2

8