Minimum Total Manhattan Distance

You are given the positions of N people on a 2D grid. The grid is infinite in both directions and each person is located at some integer coordinate (row, column). The travel time for a person is equal to the Manhattan distance from their starting position to the meeting point.

The Manhattan distance between two points \((r_1, c_1)\) and \((r_2, c_2)\) is defined as:

[ |r_1 - r_2| + |c_1 - c_2| ]

Your task is to choose a meeting point such that the total travel time of all people is minimized and output that minimum total time.

Note: It is well-known that the optimal meeting point in Manhattan distance is obtained by choosing the median of the row coordinates and the median of the column coordinates of all people.

inputFormat

The first line contains a single integer \(N\) denoting the number of people. Each of the following \(N\) lines contains two space-separated integers \(r\) and \(c\) representing the row and column positions of a person.

Example:

2
1 0
2 2

outputFormat

Output a single integer representing the minimum total time required for all people to meet at a common point.

Example:

3

## sample

2
1 0
2 2

3