题目描述

在遥远的泽塔星系 , 人类在一颗宜居行星上建立了 $\rm N$ 座星际信号塔 , 用于保障星际飞船的通信畅通

每座信号塔的位置用二维坐标 $\rm (x_i, y_i)$ 表示

信号塔之间的通信延迟由它们的曼哈顿距离决定：对于两座信号塔 $\rm (x_a, y_a)$ 和 $\rm (x_b, y_b)$ , 延迟为 $\rm |x_a - x_b| + |y_a - y_b|$

由于能源限制 , 现在需要暂时关闭其中一座信号塔进行维护

工程师需要选择关闭哪一座 , 才能让剩余所有信号塔之间的 最大通信延迟 尽可能小

请你计算出这个可能的最大延迟值的最小值是多少

输入格式

第一行输入一个整数 $\rm N$

接下来 $\rm N$ 行 , 每行包含两个空格分隔的整数 $\rm x$ 和 $\rm y$ , 表示一座信号塔的坐标

输出一个整数 , 表示答案

见 ex_data1.in

见 ex_data1.out

见 ex_data2.in

见 ex_data2.out

对于 $20\%$ 的数据 $\rm 3 \leq N \leq 100$

对于 $50\%$ 的数据 $\rm 3 \leq N \leq 5000$

对于全部的数据 $\rm 3 \leq N \leq 10^5 , -10^9 \leq x_i,y_i \leq 10^9$