P5925 [POI 2007] Natural Gas Pipeline Gaz

Mary is trying to control Chengdu’s natural gas market.

Experts have marked the best natural gas wells and transfer stations on a map of Chengdu. Now we need to connect the transfer stations and the natural gas wells. Each transfer station must be connected to exactly one well, and vice versa. Mary specifically requires that every gas pipeline must start from some natural gas well and be built only to the south or to the east. Mary wants to know how to connect each natural gas well and transfer station so that the total length of the required pipelines is minimal. A solution is guaranteed to exist.

The first line contains a positive integer $n$, the number of natural gas wells (the number of transfer stations is the same). The next $n$ lines each contain two integers $x_i$ and $y_i$, the coordinates of a natural gas well. Moving east increases the $x$ coordinate, and moving north increases the $y$ coordinate. The next $n$ lines each contain two integers $x_j$ and $y_j$, the coordinates of a transfer station.

The first line contains one number, the minimum total length of the connecting pipelines.

For $100\%$ of the testdata, $2\le n\le50000$, $0\le x_i,y_i,x_j,y_j\le100000$。 Translated by ChatGPT 5