题目描述

机器人Rob在一个有$\red{n×n}$ 个方格的方形区域$\red{F}$ 中收集样本。$\red{（i,j）}$方格中样本的价值为$\red{v(i,j)}$，如下图所示。

Rob 从方形区域$\red{F}$ 的左上角$\red{A}$点出发，向下或向右行走，直到右下角的$\red{B}$ 点，在走过的路上，收集方格中的样本。Rob 从$\red{A}$点到$\red{}$ 点共走$\red{2}$次，试找出Rob 的$\red{2}$条行走路径，使其取得的样本总价值最大。

编程任务：给定方形区域$\red{F}$中的样本分布，编程计算Rob的$\red{2}$条行走路径，使其取得的样本总价值最大。

输入格式

第$\red{1}$ 行有$\red{1}$ 个正整数$\red{n}$，表示方形区域$\red{F}$有$\red{n×n }$个方格。接下来每行有$\red{3}$ 个整数，前$\red{2}$ 个表示方格位置，第$\red{3}$个数为该位置样本价值。最后一行是$\red{3}$个$\red{0}$。

输出格式

计算最大样本总价值。

样例

输入样例

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