Description

一个点每过一个单位时间就会向 4 个方向扩散一个距离，如图所示：两个点 a 、b 连通，记作 e(a,b)，当且仅当 a 、b 的扩散区域有公共部分。连通块的定义是块内的任意两个点 u、v 都必定存在路径 e(u,a₀),e(a₀,a₁),…e(a_k,v)。

给定平面上的 n 个点，问最早什么时候它们形成一个连通块。

Input Format

第一行一个数 n ，以下 n 行，每行一个点坐标。

Output Format

输出仅一个数，表示最早的时刻所有点形成连通块。

2
0 0
5 5

5

Hint

对于 20% 的数据，满足 1 ≤ n ≤ 5,1 ≤ X_i,Y_i ≤ 50；

对于 100% 的数据，满足 1 ≤ n ≤50,1 ≤ X_i,Y_i≤ 10⁹。

Source

一本通 第二章 二分与三分