本题没有可用的提交语言。

描述

背景

在与入侵者的战斗中，农夫威廉召集了全国各地的农民一起帮助国王击败入侵者。因此，国王决定在战争胜利后奖励威廉一块巨大的农场。

问题

国王将他的国家划分为一个$A \times B$的网格，并将每个$1 \times 1$的小方格标记为一对整数。参考下面的图片作为示例： 然而，并不是所有的小方格都是可用的。有些已经被授予给其他人，有些在战争中被摧毁。因此，国王只列出了可用的小方格，并让威廉从中选择一些。同时，威廉不能选择所有的方格。他只能选择其中的一部分，使得这些方格可以形成一个连接区域来建立他的农场。一个连接区域的定义如下：

1. 一个连接区域是由一些$1 \times 1$的方格组成；
2. 从这些方格中的任何一个方格出发，都可以走到该区域内的任何一个其他方格，而不需要进入不属于该区域的方格；
3. 在站在一个方格时，可以进入四个相邻的方向：北、南、东、西。

此外，每个可用的方格都有一个值。威廉应该选择一个能够形成连接区域的农场，使得这个区域的方格值之和最大。换句话说，威廉应该选择一些方格，组成一个连接区域，其总值最大。

任务

你的任务是找出最大值。

输入

输入由多个测试用例组成。每个测试用例的第一行包含一个正整数$N$（$1 \leq N \leq 200000$），表示可用方格的数量。接下来的$N$行中，每行包含三个整数$x, y, v$，分别表示一个方格的位置$(x, y)$和它的值$v$。所有的$x$和$y$都在有符号的16位整数范围内。值$v$是一个非负整数，小于$10000$。以$0$开始的测试用例表示结束，不需要输出结果。

输出

对于每个测试用例，输出一行，表示威廉能够建立农场的最大值。

输入数据 1

1
0 0 1
6
0 1 1
0 0 1
1 0 1
2 2 2
2 1 2
2 -1 1
0

输出数据 1

1
4

来源
Atlas of rruucc@POJ