Saplings That Must Not Touch

A tree nursery is a grid plot of m rows and w columns. A cell holding -1 is a rock; any other cell holds the yield (a whole number of seedlings) a sapling planted there would give. The gardener plants at most one sapling per cell and never on a rock. Saplings must not touch: no two planted cells may share an edge or a corner.

Return the largest total yield she can plant. Planting nothing is allowed, so the answer is at least 0. An empty plot gives 0.

Examples

Input:  plot = [[5, 1, 5],
                [1, 9, 1],
                [5, 1, 5]]
Output: 20
Explanation: the four corners; the 9 touches all of them.

Input:  plot = [[3, -1, 4],
                [-1, -1, -1],
                [2, 8, 2]]
Output: 15
Explanation: 3 and 4 on the top row, 8 on the bottom row.

Input:  plot = [[-1]]
Output: 0

Constraints

• 0 <= m <= 60, 1 <= w <= 10 when m > 0, every row has length w
• every cell is -1 or between 0 and 100

Goals

• Encode the planted cells of one row as a bitmask
• List the valid row patterns and the compatible pairs of patterns once
• Run a DP down the rows whose state is the previous row's pattern