题目描述

小 G 处于一个三维空间中。一开始他在 $(-10^{100},-10^{100},-10^{100})$ 。

每一步小 G 可以从 $(x,y,z)$ 走到 $(x+1,y,z)$ 或 $(x,y+1,z)$ 或 $(x,y,z+1)$ ，最终他要走到 $(10^{100},10^{100},10^{100})$ 。

在途中的整点上小 G 可以射击。现在有 $n$ 只野兽，坐标会被给出。

假设小 G 的枪射程是 $k$ ，那能从 $(x_0,y_0,z_0)$ 射到 $(x_1,y_1,z_1)$ 的野兽当且仅当 $\max(|x_0-x_1|,|y_0-y_1|,|z_0-z_1|)\le k$ 。

小 G 的枪法百发百中，子弹有 $10^{100}$ 颗。他希望能在走路的过程中射掉所有野兽，请求出枪的射程 $k$ 最小是多少？

输入格式

第一行一个整数 $n$ ，表示猎物的数量。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i,z_i$ ，表示野兽 $i$ 所在的坐标 $(x_i,y_i,z_i)$ 。

输出格式

输出一行一个整数，表示所需的最小射程 $k$ 。

样例

样例输入

5
1 1 4
5 1 4
1 9 1
9 8 1
0 0 0

样例输出

2

数据范围

对于所有数据，$1 \le n\le 5*10^5$ ，对于 $1\le i\le n$ ， $0\le x_i,y_i,z_i\le 10^9$。

子任务 1 ( 20% ) : $n\le 10$ 。

子任务 2 ( 20% ) : $n\le 100$ 。

子任务 3 ( 20% ) : $n\le 1000$ 。

子任务 4 ( 20% ) : 对于 $1\le i\le n$ ，$x_i=0$。

子任务 5 ( 20% ) : 无特殊限制。