题目描述

A 国是一个拥有很多岛屿的国家。岛屿上的风景迷人且各有特点。不但如此，这些岛屿都是圆形的。所有的一切吸引了很多国内外的游客，A 国当然不会放弃这个发展经济的好机会了。为了更好发展旅游业，A 国决定由 S 航空公司来设计生产用于往返于各个岛屿之间的旅游小型机。

A 国拥有大量的能源资源，但是缺乏航空技术。航空公司的工程师们在设计旅游小型机的时候总是希望能够减小油箱的大小而降低设计难度。由于每个岛屿上都有加油站，即使油箱容积小点，也可以通过到一些中转岛屿加油的办法往返于任意两个岛屿之间。A国拥有大量的能源，因而中转带来的资源浪费它们并不关心。

已经知道，飞行 1 km 需要 1 个单位的汽油。如果油箱过小，可能出导致飞行中由于汽油竭尽而坠入大海的危险。另外如果油箱过大，又会增加设计难度。因此，工程师们希望知道最小的油箱容积是多少？

岛屿的数目是那么多，工程师们一时都很难计算出：旅游小型机最小需要多大的油箱才能够保证可以往返于任意两个岛屿之间？聪明的你能否编写一个程序来帮助繁忙的工程师们呢。

输入格式

第一行：一个整数 N ( 1 < N <= 1000 )

接下来 N 行,每行包括 3 个整数 (x , y , r )，分别表示 N 个岛屿的坐标 ( x , y ) 及其它们的半径。

输出格式

一个整数 V ( V 是保证可以往返于任意两个岛屿之间的旅游小型机的最小油箱容积 )。

样例

3
0 0 1
3 0 1
0 4 1

2

提示

输入样例中 A 岛位于 (0,0) ，半径为1 ; B 岛位于 (3,0) ，半径为 1 ; C 岛位于 (0,4) ，半径为 1 。从 A 岛到达 B 岛的最近距离需要 1 个单位的汽油。从 A 岛到达 C 岛的最近距离需要 2 个单位的汽油。直接从 B 岛到达 C 岛需要 3 个单位的汽油，也就是说需要 3 个单位大小的油箱。但是，假如先从 B 岛飞到A岛，然后再从 A 岛飞到 C 岛，那么就只需要一个 2 个单位大小的油箱。所以，样例的正确输出应当是 2 。