C - King's Summit Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10^9 行 10^9 列のグリッドがあり、このグリッドの上から i 番目、左から j 番目のマスをマス (i, j) と表記します。

グリッド上には N 人の人がおり、はじめ i 人目の人はマス (R_i, C_i) にいます。

はじめ時刻は 0 であり、各人は、時刻 1, 2, 3, 4, \ldots に以下のような移動をすることができます。

  • その場に留まるか、8 近傍のマスに移動する。ただし、グリッドの外側に出ることはできない。厳密には、現在いるマスをマス (i, j) としてマス (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) のうち存在するマスのいずれかに移動する。また、移動には時間がかからないものとする。

N 人の人が全員同じマスに集まる時刻として考えられる最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq R_i, C_i \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
R_1 C_1
R_2 C_2
\vdots
R_N C_N

出力

答えを出力せよ。

入力例 1

3
2 3
5 1
8 1

出力例 1

3

以下のようにそれぞれの人が移動することによって、全員が時刻 3 にマス (5, 4) に集まります。

  • 時刻 1 では、1 人目の人はマス (3, 4)、2 人目の人はマス (6, 2)、3 人目の人はマス (7, 2) に移動する。

  • 時刻 2 では、1 人目の人はマス (4, 4)、2 人目の人はマス (5, 3)、3 人目の人はマス (6, 3) に移動する。

  • 時刻 3 では、1 人目の人はマス (5, 4)、2 人目の人はマス (5, 4)、3 人目の人はマス (5, 4) に移動する。

入力例 2

5
6 7
6 7
6 7
6 7
6 7

出力例 2

0

はじめからすべての人は同じマスにいます。

入力例 3

6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926

出力例 3

44

Score : 300 points

Problem Statement

There is a grid with 10^9 rows and 10^9 columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

There are N people on the grid. Initially, the i-th person is at square (R_i, C_i).

The time starts at 0. Each person can do the following move at times 1, 2, 3, 4, \ldots.

  • Stay at the current position, or move to an 8-adjacent square. It is forbidden to leave the grid. Formally, let square (i, j) be the current square, and move to one of the squares (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) that exists. Assume that the move takes no time.

Find the minimum possible time when the N people are at the same square.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq R_i, C_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
R_1 C_1
R_2 C_2
\vdots
R_N C_N

Output

Output the answer.

Sample Input 1

3
2 3
5 1
8 1

Sample Output 1

3

All people will be at square (5, 4) at time 3 if each person moves as follows.

  • At time 1, the 1st person moves to square (3, 4), the 2nd person moves to square (6, 2), and the 3rd person moves to square (7, 2).

  • At time 2, the 1st person moves to square (4, 4), the 2nd person moves to square (5, 3), and the 3rd person moves to square (6, 3).

  • At time 3, the 1st person moves to square (5, 4), the 2nd person moves to square (5, 4), and the 3rd person moves to square (5, 4).

Sample Input 2

5
6 7
6 7
6 7
6 7
6 7

Sample Output 2

0

All people start at the same square.

Sample Input 3

6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926

Sample Output 3

44