## Another Contest 3 Problem 2 - Camelot

View as PDF

Points: 15
Time limit: 1.0s
PyPy 3 1.5s
Memory limit: 256M

Problem type

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.

#### Constraints

Kings may already be in the same square.

#### Input Specification

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 Specification

Output the minimum time in seconds needed for all the kings to convene.

#### Sample Input

4
1 1
1 3
1 2
1 10

#### Sample Output

10