Minimum Copper Consumption on PCB

The Printed Circuit Board (PCB) is used to mount electronic components and connect them using copper lines. In our problem, you are given several electronic components on a rectangular board. The copper lines that connect these components must be parallel to the board edges (i.e. horizontal or vertical) and have a fixed width. Your task is to connect all the components with copper wires such that the total length of the copper used is minimized.

This problem can be modeled as finding a minimum spanning tree (MST) over the points, where the distance between two points is defined by the Manhattan distance:

\( d((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2| \)

You are to compute the minimum copper consumption required to connect all electronic components.

inputFormat

The first line contains an integer n (\(1 \leq n \leq 1000\)), representing the number of electronic components on the PCB. Each of the next n lines contains two integers x and y (\(-10^4 \leq x, y \leq 10^4\)), representing the coordinates of a component.

outputFormat

Output a single integer that is the minimum total length of copper required to connect all the components.

sample

2
0 0
1 1

2