Convenience Store 2

Interview

Time limit2sMemory limit512 MB

Summary

Given n customer points, place one store anywhere to minimize the total Manhattan distance to all customers and print that minimum sum.

Level: Medium5 of 10
Topics: Math, Sorting, Greedy, Geometry
Solved: No attempts yet

Problem

Youngseon plans to start a convenience store. Most of the preparation is done, but the store's location is not decided yet. From market research, Youngseon knows where the main customers are, and wants to place the store so that the sum of the distances to all customers is as small as possible. The distance between two locations $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$ .

You are given the locations $(x_i, y_i)$ of $n$ main customers. If the store is built at a location that minimizes the sum of distances to all customers, what is that minimum sum?

Input

The first line contains $n$ , the number of main customers.

Each of the next $n$ lines contains the location $x_i$ , $y_i$ of customer $i$ , separated by a space.

Output

Print the minimum possible sum of distances from the store to all customers, as an integer.

Constraints

$1 \le n \le 100\,000$
$-1\,000\,000 \le x_i, y_i \le 1\,000\,000$
All input values are integers.

Examples1

Example 1
Input
```
5
2 2
3 4
5 6
1 9
-2 -8
```
Expected output
```
30
```