Another Contest 3 Problem 2 - Camelot

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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