Convenience Store 2

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?

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.

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

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