Point

Time Limit: 40000/20000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

There are a lot of points on a plane. We need to find the closest point for each point. To be special, “closest” refers to unusual distance: the distance of two points A, B is defined by this:
Distance (A, B) = max (|Ax – Bx|, |Ay – By|)
Please output the sum of the distances.

Input

The input consists of multiply test cases. The first line of each test case contain one integer, n (2 <= n <= 100000), which is the number of points. Each of the next n lines contains two integer, x, y (0 <= x, y <= 1000000000), indicating the coordinate of a point. Two points might have the same coordinate.

Output

Output the sum of the distances.

Sample Input

3 0 0 1 1 3 3

Sample Output

4

Hint

lcy

Source

HDOJ Monthly Contest – 2010.04.04

提交代码