题目描述

小 Y 的朋友小 L 带她参观了一家无人机企业的新技术展示。

展示场地是一个巨大的三维空间，用整数三元组 $(x,y,z)$ 表示一个点的坐标。

这家企业在三维空间中放置了 $n$ 个基站，第 $i$ 个基站的位置为 $(x_i,y_i,z_i)$（$-10^9\le x_i,y_i,z_i\le 10^9$），可以有多个基站放在相同的位置上。

现在有一架无人机，它的位置 $(x_p,y_p,z_p)$ 初始为 $(-10^{10},-10^{10},-10^{10})$，接下来它要展示如何激活所有基站。

在展示过程中，每秒无人机会移动到 $(x_p+1,y_p,z_p),(x_p,y_p+1,z_p),(x_p,y_p,z_p+1)$ 中的其中一个位置上。

无人机每次移动后，所有满足 $|x_i-x_p|\le k,|y_i-y_p|\le k,|z_i-z_p|\le k$ 的未激活基站 $i$ 都会被激活，其中 $k$ 是一个非负整数，表示无人机的信号强度。

现在小 L 想知道，如果用最理想的方式安排无人机的行动路线，那么无人机的信号强度 $k$ 至少要是多少，才能激活所有基站。

输入格式

从文件 drone.in 中读入数据。

第一行一个整数 $n$，表示基站的数量。

第 $i+1$（$1\le i\le n$）行，三个整数 $x_i,y_i,z_i$，表示第 $i$ 个基站的位置。

输出格式

输出到文件 drone.out 中。

输出一行一个整数，表示最优情况下无人机信号强度的最小值。

样例 1 输入

3
1 2 3
-1 -5 -2
6 8 -5

样例 1 输出

3

样例 1 解释

依次经过 $(-1,-5,-5),(3,5,-5),(3,5,3)$ 并分别激活基站 $2,3,1$ 即可。

样例 2

见选手目录下的 drone/drone2.in 与 drone/drone2.ans。

该样例满足子任务 $1$ 的约束条件。

样例 3

见选手目录下的 drone/drone3.in 与 drone/drone3.ans。

该样例满足子任务 $2$ 的约束条件。

样例 4

见选手目录下的 drone/drone4.in 与 drone/drone4.ans。

该样例满足子任务 $3$ 的约束条件。

样例 5

见选手目录下的 drone/drone5.in 与 drone/drone5.ans。

该样例满足子任务 $4$ 的约束条件。

样例 6

见选手目录下的 drone/drone6.in 与 drone/drone6.ans。

该样例满足子任务 $5$ 的约束条件。

样例 7

见选手目录下的 drone/drone7.in 与 drone/drone7.ans。

该样例满足子任务 $6$ 的约束条件。

样例 8

见选手目录下的 drone/drone8.in 与 drone/drone8.ans。

该样例满足子任务 $7$ 的约束条件。

数据范围

对于所有测试数据，保证 $1\le n\le 5\times 10^5,-10^9\le x_i,y_i,z_i\le 10^9$。

子任务编号	$n$	特殊性质	分值
$1$	$n\le 10$	无特殊性质	$10$
$2$	$n\le 18$	^	$20$
$3$	$n\le 5\times 10^5$	特殊性质 A	$15$
$4$	$n\le 300$	无特殊性质
$5$	$n\le 5\times 10^5$	特殊性质 B
$6$	$n\le 2000$	无特殊性质	$10$
$7$	$n\le 5\times 10^5$	^	$15$

特殊性质 A：对于所有 $1\le i\le n$，均有 $x_i+y_i=0$ 且 $z_i=0$。

特殊性质 B：所有 $z_i$ 相等。

本题开启所有合理的子任务依赖。