背景

鹫见芹娜，救护骑士团 唯一靠谱 的医护人员，以“救护”为己任和座右铭。虽然身怀绝技，掌握破解密码、打开门锁、瞬间移动、心灵感应等多项特工技能(?)。在病患频繁多源地出现时，仍然感到分身乏术。

而所谓孵化器，正是运用创新思维和技术解决现实问题的高尚实验室！孵化创新技术，孵化创新人才，孵化创新企业！

大哉，孵化器道！

运用孵化器开发的四轴飞行器，搭载合适的外设，从此，针对病情并不严重的患者，芹娜只需要驾驶无人机前往诊断，运用无人机上的微型打印机给出诊断结果和药方，请患者自行前往药房购置药物。

不用瞬间移动了呢。

题目描述

救护准备！

无人机电池电量有限，为了尽可能发扬“救护”之道，需要令无人机的每一次往返都尽可能多地救护患者。然而，芹娜作为医护人员，不可能放弃紧张的救护时间用于规划路径。因此，路径规划需要写在无人机的程序里。

A
  0  0  0  0  0  0  0  0
  0  0 13  0  0  6  0  0
  0  0  0  0  7  0  0  0
  0  0  0 14  0  0  0  0
  0 21  0  0  0  4  0  0
  0  0 15  0  0  0  0  0
  0 14  0  0  0  0  0  0
  0  0  0  0  0  0  0  0
                         B

每一次救护都可以等价于发生在如上的地图中。其中，芹娜所在的救护骑士团本部位于地图左上角A点，无人机中继站位于右下角B点。无人机必须在每次飞行中由A驶向B进行充电和检修，然后返航回到A。

由于无人机单次飞行电量不支持大于(地图行列数$n \times 2-2$)曼哈顿距离的移动，无人机在由A向B行进时只能右移或者下移，由B向A返航时只能左移或者上移。

地图上的每个数字可以认为一个区域内，根据病人数量、病情严重程度、流行病传染能力等因素计算得到的权，权越大，则越具有救护意义。路径规划程序必须保证在满足如上要求的前提下，在一次往返中取得尽可能大的权。

很显然，在由A向B行进时已经救护的区域不需要再次救护，因而重复驶过该区域不会再次得到该区域的权。

“无人机不可以做外科手术。不过无论如何，花绘酱，为什么提到加装电锯的时候你会这样兴奋……？”

Format

Input

依据地图比例尺的不同，地图上的区域划分也有所不同。

输入的第一行包含一个整数，代表救护发生在划分为$n \times n$个区域的地图中。

此后的每一行包含三个整数，前两个数代表区域在地图上的位置，第三个数代表权的大小。

Output

一个整数，代表可能取得的最大的权之和。

Samples

8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14

67

Limitation

1s, 1024KiB for each test case.

对于100%的数据，有$n \leq 10.$

宽松的格式检查~

不必拘泥于那几个空格和回车。

“放松，朋友！多一点少一点没什么关系！”