题目描述

一个点每过一个单位时间就会向四个方向扩散一个距离，如图。

两个点 a 、 b 连通，记作 e(a,b)，当且仅当 a,b 的扩散区域有公共部分。连通块的定义是块内的任意两个点 u,v 都必定存在路径 e(u,$a_{0}$),e($a_{0}$,$a_{1}$),⋯,e($a_k$,v)。给定平面上的 n 个点，问最早什么时刻它们形成一个连通块。

输入格式

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

输出格式

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

数据范围与约定

对于 100% 的数据，满足 $1\le N\le 50$，$1\le X_i,Y_i\le 10^{9}$。

可见测试数据

输入数据 1

2
0 0
5 5

输出数据 1

5

输入数据 2

5
5 5
7 8
6 8
5 8
4 6

输出数据 2

2

输入数据 3

5
32 19
21 14
44 2
48 13
19 23

输出数据 3

11