Picking Numbers on a Grid

Problem Description

There is an $N\times N$ grid $(N\le 9)$. Some cells contain a positive integer, while others contain $0$. As shown in the figure below (see sample):

A person starts from point $A$ at the top-left corner and can only move down or right, until reaching point $B$ at the bottom-right corner. Along the way, he can pick up the number in a cell (the cell then becomes $0$). This person walks from $A$ to $B$ twice. Find $2$ such paths so that the sum of the numbers picked is maximized.

Input Format

The first line of input is an integer $N$ (indicating the $N\times N$ grid). Each of the following lines contains three integers: the first two indicate a position, and the third is the number placed at that position. A single line of 0 indicates the end of input.

Output Format

Output a single integer: the maximum sum obtained along the $2$ paths.

Sample Input 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

Sample Output 1

67

Constraints

$1\le N\le 9$.