Cherry Picking Round Trip

An orchard is a square grid field with n rows and n columns. Each cell holds 1 (a tree with one ripe cherry), 0 (empty grass) or -1 (a thorn bush you cannot walk through).

You start in the top-left cell and walk to the bottom-right cell, moving only right or down. Then you walk back to the top-left cell, moving only left or up. Whenever you step on a cell with a cherry you pick it and the cell becomes empty, so a cherry is picked only once even if both walks pass it.

Write max_cherries(field) that returns the most cherries you can pick on the round trip. If thorn bushes block every way to the bottom-right cell, return 0.

Examples

max_cherries([[1, 1, 0], [0, -1, 1], [1, 1, 1]])  # returns 6
max_cherries([[1, 1, 1], [1, 1, 1], [1, 1, 1]])   # returns 8
max_cherries([[1, -1], [-1, 1]])                  # returns 0

In the first example the two walks pass on different sides of the thorn bush and pick all six cherries. In the second, the two walks can cover at most eight of the nine cells.

Constraints

• 1 <= n <= 40
• Every cell is -1, 0 or 1.
• The top-left and the bottom-right cell are never -1.