Hide

# Grid MST

This is a very simple problem. You are given $N$ points. Some points may be repeated. The weight (distance) between two points is given by the Manhattan distance between the two points. Find the weight of a Minimum Spanning Tree that spans these $N$ points.

## Input

The input consists of:

• One line with one integer $N$ ($1 \leq N \leq 100\, 000$), the number of points,

• $N$ lines each with two integers $x$ and $y$ ($0 \leq x,y < 1\, 000$), the coordinates of each point.

## Output

Output one line with a single integer: The weight of a Minimum Spanning Tree that spans these $N$ points.

Sample Input 1 Sample Output 1
4
0 0
0 1
1 0
1 1

3

Sample Input 2 Sample Output 2
5
0 0
10 0
10 0
11 1
12 2

14

CPU Time limit 4 seconds
Memory limit 1024 MB
Difficulty 7.3hard
Statistics Show