There is an infinite integer grid where N people live in N different houses. They decide to create a meeting point at one person's house.
From any given cell, all 8 adjacent cells can be reached in 1 unit of time, e.g. (x,y) can be reached from (x-1,y+1) in one unit of time. Find a common meeting place which minimizes the combined travel time of everyone.
A positive integer N that denotes N houses or people.
The following N lines will contain two integers x,y each that denote the coordinates of the respective house.
An integer, M, that denotes the minimum combined travel time of everyone.
N <= 105
The absolute value of each co-ordinate in the input will be at most 109
HINT: You may need 64-bit integer.
The houses will have a travel-sum of 11, 13, 8, or 10. 8 is the minimum.