Description

朋友的家可表示为二维平面的网格。Mirko 在行走时，可以朝 $8$ 个方向移动，每次都是整数坐标。他每一步朝上、下、左、右以及 $4$ 个对角方向走一格。

每个朋友的家可表示为平面上的点 $(x,y)$。当 Mirko 到某朋友家送票时，朋友也可以走出来迎接他，也可以向 $8$ 个方向行走。因此，Mirko 和这个朋友最多可以在距离他家 $P$ 步远的位置相遇。$P$ 随每个朋友不同。

Mirko 的起始位置与终点位置都未知。

请求出 Mirko 送完所有票的最少移动步数。

Input Format

第一行一个整数，表示 Mirko 的朋友数 $N (2 ≤ N ≤ 200{,}000)$；

接下来 $N$ 行，每行 $3$ 个数，分别表示 $x,y,P\ (0 ≤ x, y, P ≤ 200{,}000)$。朋友按 Mirko 送票的顺序给出。

Output Format

共一行一个整数，表示 Mirko 必须走的最少移动步数。

3
3 10 2
8 4 2
2 5 2

4

4
3 3 5
7 11 5
20 8 10
30 18 3

19

Hint

对于全部数据，保证 $2 ≤ N ≤ 200{,}000$，$0 ≤ x, y, P ≤ 200{,}000$。