You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

####题目描述 wxl要去食堂吃饭然后再回到出发点。由于wxl的RP非常好，以至于在去食堂的路上会捡到钱。学校是一个 $n$ 行n列的矩阵。 shl在矩阵的左上角 ，坐标 $(1,1)$ ，食堂在矩阵的右下角，坐标 $(n,n)$ 。wxl非常懒，不希望绕远路，所以去食堂的路上只可以向下或者向右走，而回来的路上只可以向上或者向左走。在去食堂和回去的路上，wxl可能会在地上捡到钱，但是尽管wxl的RP很好，可每个地方只能捡到一次钱。也就是说如果wxl去食堂时捡到了某个点的钱，回来时就没钱了。反之亦然。告诉你每个地方的钱有多少，没有钱用 $0$ 表示（保证出发点和食堂为 $0$ ），问shl最多可以捡到多少钱。 ####输入格式 第一行为一个整数 $n$ 。

接下来的每行有三个整数，前两个表示位置，第三个数为该位置上可以捡到的钱。

最后一行单独的 $0$ 表示输入结束。 ####输出格式 只需输出一个整数，表示wxl来回可以捡到最多的钱 ####样例1输入

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
0 0 0

####样例1输出

67

####数据范围与提示 对于 $30\%$ 数据满足, $1≤n≤5$ 。

对于 $60\%$ 数据满足，$1≤n≤20$ 。

对于 $100\%$ 数据满足， $1≤n≤50$ , $1≤每个地方捡到的钱≤10000$ 。