P1004 [NOIP 2000 Senior] Collecting Numbers on a Grid

NOIP 2000 提高组 T4

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.

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 a single integer, the maximum total collected along the two paths.

Constraints: $1 \le N \le 9$. Translated by ChatGPT 5