Plumber

Our favourite plumber is on his way to save the princess located in the castle. The castle is represented by a 2-D grid that contains obstacles (denoted by `-1`) and coins (denoted by `1`). Empty squares in the castle are denoted by `0`.

Our plumber will always start at the first row in the grid and the princess will always be at the last row in the grid. On the plumber's way to save the princess (reach any position in the last row), what is the maximal number of coins that can be obtained?

Restrictions:

• The plumber can only move down, right, and left, but never up.
• The plumber cannot move through the obstacles.

If the plumber cannot reach the last row, return `-1`.

Input

• `grid`: Grid containing the castle layout

Output

Integer representing the maximal number of coins that can be obtained, return `-1` if the plumber cannot reach the last row.

Examples

Example 1:

Input:

``1grid = [[0, 0], [1, 1]]``

Output: `2`

Explanation:

Both of the coins can be collected on the way to the princess.

Example 2:

Input:

``1grid = [[0, 0, 1], [0, 0, -1], [0, 0, 0]]``

Output: `1`

Explanation:

After getting the coin in the first row, the plumber can move to the left and down to avoid the obstacle.

Example 3:

Input:

``1grid = [[1,0,-1,1,0,1],[1,-1,1,-1,1,-1],[0,0,-1,-1,1,1]]``

Output: `5`

Explanation:

See solution.

Constraints

• `2 <= rows, columns <= 2000`

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. `Lorem` `Ipsum` has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, `Lorem` `Ipsum` is not simply random text.

``````1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3``````