Description

Consider an $N \times N$ grid ($N \le 9$). Some cells are filled with positive integers, while the others contain the number $0$. As shown below (see the sample):

A person starts from the top-left corner point $A$, and may move either down or right until reaching the bottom-right corner point $B$. Along the way, he may collect the numbers in the cells he visits (after which those cells become the number $0$).
This person travels from $A$ to $B$ twice. Find two such paths that maximize the total sum collected.

Input Format

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

Output Format

Output a single integer, the maximum total collected along the two paths.

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

67

Hint

Constraints: $1 \le N \le 9$.

Translated by ChatGPT 5