3212: 寻找魔法正方形

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:8 解决:7

题目描述

在古老的仙境中,有一个神秘的谜题被传承了数百年。据说,很久以前,一位智者发现了一块神奇的石板,上面刻满了精密的几何图案和蕴含着无尽智慧的编码。这块石板揭示了如何用一块神奇的魔法纸覆盖散落在仙境平面上的许多神秘圆圈。

这些圆圈代表着仙境中的不同奥秘,每个圆圈都散发着独特的能量。人们渴望保护这些圆圈,因为它们代表着平衡和和谐。然而,时间的流逝使得这些圆圈逐渐散布开来,形成了一幅富有挑战的几何图景。

传说中,智者曾经通过数学和魔法创造了一个魔法正方形,能够将所有的圆圈完美地包裹其中。这个正方形不仅保护了圆圈的力量,还让仙境继续保持着秩序和和平。然而,这个魔法已经失传多年,留下了一个谜题,等待着新的勇者来解开。

你现在就是这个仙境的新勇者,传承了智者的智慧,你的使命是恢复这个魔法,找到那个神奇的魔法正方形,将散落的圆圈重新团聚起来,为仙境带来新的和谐。时间紧迫,仙境的命运掌握在你的手中。使用你的智慧,找到那个能够与 x 轴和 y 轴平行的正方形,让圆圈重新发挥它们的神奇力量,创造出美丽而宁静的景象。

输入

第一行是正数 n

然后有 n 行数据,每行数据有 x,y,r 分别表示该圆的圆心整数坐标 ( x,y )与整数半径 r


输出

输出能覆盖以上多个圆的最小正方形的边长。

样例输入 复制

3
1 1 1
2 2 1
3 1 2 

样例输出 复制

5

提示





输入

1
0 0 1

输出

2
【样例1解释】 


按照图可见要能覆盖所有的圆,这个正方形的边长至少为 5



【数据范围】

1 <= n,r <=1000

-1000 <= x,y <= 1000