Minimum Cost to Connect All Points

Problem statement

A campus must connect all its sensor points using cables. A cable between two points costs their Manhattan distance, and the network may connect points indirectly through other sensors to reduce total cost. Your task Find the minimum total cost of edges that connect all points. The cost between (x1, y1) and (x2, y2) is abs(x1-x2) + abs(y1-y2). Important details Every pair of points is a possible edge. You need a connected network, not a separate direct cable from the first point to every other point. A minimum spanning tree provides the required cost; a single point costs zero. Worked example For points (0, 0), (2, 0) and (2, 3), use edges of costs 2 and 3 for a total of 5. The direct first-to-last edge alone would not connect the middle point.

Input format

First line: n. Next n lines: x y coordinates.

Output format

Print the minimum connection cost.

Constraints

1 <= n <= 1000; -1000000 <= coordinates <= 1000000; points are distinct; use 64-bit totals.

Sample input

3
0 0
2 0
2 3

Sample output

5