In the game of chess, a king can move horizontally, vertically, or diagonally by one unit. More specifically, if a king is at , their -coordinate can change by at most one and their -coordinate can change by at most one in a single move.
There are kings on an infinite chessboard where each square can fit an infinite number of kings, and they wish to meet up at a single location. In one second, exactly one king can move by one unit - all other kings must stay still. Compute the minimum amount of time needed for all the kings to meet up.
Kings may already be in the same square.
The first line contains a single positive integer, .
Each of the next lines contains two space-separated integers, and , indicating that a king is at .
Output the minimum time in seconds needed for all the kings to convene.
4 1 1 1 3 1 2 1 10