On a hike!#11059
In the land of Smeshariki, a new season has begun! Now all the heroes are setting out on a journey. To do this, they need to gather at a single point, and from there continue their quest to conquer the world. Losyash, who coordinates the actions of the Smeshariki, knows the coordinates of all the participants. Help him determine the minimum number of seconds required for all the Smeshariki to gather together.
Initially, each Smesharik is located at a node of the integer grid. If a Smesharik is at point , then in one second they can move to one of the points (x, y + 1), (x + 1, y), (x - 1, y), (x, y - 1), or remain at .
The first line contains a single integer n~(1 \le n \le 200000) — the number of Smeshariki. The next lines specify their initial positions. Each position is given by two integers x_i and y_i~(-10^{18} \le x_i, y_i \le 10^{18}).
Print the minimum number of seconds required for all the Smeshariki to gather at a single point.
Example 1
Example 2
Example 3