P1004 [NOIP 2000 Advanced Group] Picking Numbers in a Grid

Background

NOIP 2000 Advanced Group T4

Description

Consider an \(N \times N\) grid \((N \le 9)\). Some of the cells are filled with positive integers, while others contain the number \(0\). An example is shown in the figure below (see sample):

A person starts at the top-left corner \(A\) and may move either right or down, until reaching the bottom-right corner \(B\). Along the path, the person collects the numbers in the cells (once collected, the cell becomes \(0\)).
This person travels from \(A\) to \(B\) twice. Find \(2\) such paths so that the total sum of collected numbers is maximized.

Input

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

Output

Output a single integer, the maximum sum of numbers collected along the \(2\) paths.

Sample #1

Input #1Output #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

67

Note / Hint

Data range: \(1 \le N \le 9\).