P4612 [COI 2012] SETNJA

Mirko 要给朋友们送音乐会门票。

朋友的家可表示为二维平面的网格。Mirko 在行走时，可以朝 $8$ 个方向移动，每次都是整数坐标。他每一步朝上、下、左、右以及 $4$ 个对角方向走一格。 每个朋友的家可表示为平面上的点 $(x,y)$。当 Mirko 到某朋友家送票时，朋友也可以走出来迎接他，也可以向 $8$ 个方向行走。因此，Mirko 和这个朋友最多可以在距离他家 $P$ 步远的位置相遇。$P$ 随每个朋友不同。 Mirko 的起始位置与终点位置都未知。 请求出 Mirko 送完所有票的最少移动步数。

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

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

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