Maximum Sum from Two Monotonic Paths in a Grid

Given an N×N grid (with N ≤ 9), each cell of the grid contains either a positive integer or the number 0. A person starts at the top‐left corner A and must travel to the bottom‐right corner B. The allowed moves are only to the right or downward. On the way, when the person steps into a cell, he collects the number in that cell—the cell then becomes 0. The person makes two trips from A to B. Find two paths (each from A to B, moving only down or right) so that the total sum of the numbers collected (note: if a cell is visited by both trips the number is collected only once) is maximized.

Note: This problem is equivalent to the well known "Cherry Pickup" problem. Two paths are chosen such that the union of cells visited yields the maximum sum.

inputFormat

The input begins with a single integer N (1 ≤ N ≤ 9), indicating the size of the grid. The following N lines each contain N space‐separated integers. Each integer is either 0 or a positive number.

For example, a 3x3 grid:

3
3 0 3
0 5 0
3 0 3

outputFormat

Output a single integer representing the maximum sum that can be collected by taking two paths from the top‐left corner to the bottom‐right corner.

sample

3
3 0 3
0 5 0
3 0 3

14