Minimum Pipeline Connection

Experts have marked the best natural gas wells and transfer stations on a map of Chengdu. Your task is to connect the wells and the transfer stations with pipelines, under the following constraints:

• There are exactly n natural gas wells and n transfer stations.
• Each transfer station must be connected to exactly one natural gas well, and vice versa.
• Every pipeline must start from a natural gas well and extend either east or south.

This means that if a well is located at (x, y) and a transfer station is at (p, q), a pipeline can be built only under one of the following conditions:

• Eastward: if \( q = y \) and \( p > x \); the cost is \( p - x \).
• Southward: if \( p = x \) and \( q < y \); the cost is \( y - q \).

Your goal is to determine a one-to-one pairing between wells and transfer stations such that the total pipeline length (i.e. the sum of the costs) is minimized.

Note: It is guaranteed that a valid matching exists.

inputFormat

The input begins with an integer n indicating the number of natural gas wells (and transfer stations).

This is followed by n lines each containing two integers x y representing the coordinates of each well.

After that, there are n lines each containing two integers p q representing the coordinates of each transfer station.

outputFormat

Output a single integer, the minimum total length of pipelines required to connect each well with a unique transfer station following the construction rules.

sample

2
0 0
1 1
2 0
1 0

3