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 100000$), the number of points,
 - $N$ lines each with two integers $x$ and $y$ ($0 \leq x,y < 1000$), 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.

-----Examples-----
Sample Input:
4
0 0
0 1
1 0
1 1
Sample Output:
3

Source: kattis | Difficulty: HARD
Tags: Graph algorithms


Solutions: