Gas Pipelines

The GasBit company plans to dominate the gas market in Byteotia. Analysts have already marked the best gas extraction points and distribution stations on the map. The remaining task is to assign the distribution stations to the extraction points: every distribution station must be connected to exactly one extraction point, and every extraction point to exactly one distribution station.

GasBit builds each pipeline so that it runs from an extraction point to a distribution station moving only south or east. Seen from above, a pipeline is an orthogonal broken line whose consecutive segments alternate between running south and running east, each segment perpendicular to the previous one. Because a pipeline can only go south or east, a station can be served by an extraction point only when it lies to the south-east of that point; the length of such a pipeline equals the Manhattan distance between the two points, that is $(x' - x) + (y - y')$.

The board wants to choose the assignment that minimises the total length of all the pipelines that have to be built. Pipelines may freely cross one another, since colliding pipes can be laid at different depths underground.

Write a program that reads the planned locations of the extraction points and distribution stations and outputs the minimal total length of the pipelines needed to connect them.

The first line contains one integer $n$ ($2 \le n \le 50\,000$), the number of extraction points (equal to the number of distribution stations).

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 100\,000$), separated by a single space, giving the coordinates of an extraction point. Moving east increases $x$, and moving north increases $y$.

Each of the following $n$ lines contains two integers $x'_j$ and $y'_j$ ($0 \le x'_j, y'_j \le 100\,000$), separated by a single space, giving the coordinates of a distribution station.

Extraction points and distribution stations are numbered from $1$ to $n$ in the order they appear in the input. No coordinate pair occurs more than once. It is guaranteed that at least one assignment of stations to points can be realised using pipelines that run only south or east.

Print a single integer: the minimal total length of all the gas pipelines that must be built.