A rescue operation has n crews at integer coordinates on a grid. They must all travel to one common meeting point, which itself must have integer coordinates. The cost for a crew is the Manhattan distance from its position to the meeting point. Choose the meeting point that minimizes the sum of all crews' costs, and report that minimum total cost.
Input format
Line 1: an integer n, the number of crews.
Next n lines: two integers x y, the position of a crew.
Output format
A single integer: the minimum possible total Manhattan distance.
Constraints
- 1 <= n <= 100000
- -1000000000 <= x, y <= 1000000000