Minimum Delivery Time

You are given a set of delivery points on a 2D plane. A delivery truck must visit all these points exactly once. The time taken to travel between two points is determined by the Chebyshev distance, which is defined as

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

Your task is to compute the minimum total time required for the truck to complete the delivery route. The truck can visit the points in any order.

The input consists of one or more test cases. Each test case starts with an integer k indicating the number of delivery points. It is followed by k lines each containing two integers representing the coordinates of a delivery point. A test case starting with 0 indicates the end of input and should not be processed.

inputFormat

The input is read from stdin and consists of multiple test cases. Each test case is formatted as follows:

• The first line contains an integer k (1 ≤ k) denoting the number of delivery points.
• The next k lines each contain two space-separated integers representing the x and y coordinates of a delivery point.
• A test case with k = 0 marks the end of the input.

Multiple test cases can appear consecutively. All input should be read from stdin.

outputFormat

For each test case, output a single line containing the minimum total time required for the truck to complete the delivery route. The output for each test case should be printed on a new line to stdout.

## sample

3
1 1
2 2
3 3
0

2

</p>