Airport Limousine (Maximum Passengers Collected) (Also for Core/Database Intern :)

Go from the top-left to the bottom-right moving only right/down, then return moving only left/up. −1 is a wall, 0 is an empty cell, and 1 is one passenger; once a cell is passed, its passenger is picked up and not counted again. If there is no valid outbound path, return 0. Find the maximum total number of passengers.

输入格式

The first line contains n, followed by n lines of the matrix. 1≤n≤100, and each cell is −1, 0, or 1. The start and end cells may also hold a passenger or a wall; if either is a wall, there is no valid trip.

输出格式

Output the single integer required by the problem.

样例 1

输入：

2
0 1
-1 0

输出：

1

样例 2

输入：

3
0 1 -1
1 0 -1
1 1 1

输出：

5

样例 3

输入：

1
1

输出：

1

样例说明

The answers to the three public examples are, in order: 1; 5; 1. The examples were rechecked by independent enumeration, state search, or direct simulation.