Maximum Path Sum in Grid

You are given a grid of positive integers. Your task is to determine the maximum sum that can be obtained by moving from the top-left corner \( (0,0) \) to the bottom-right corner \( (m-1,n-1) \) of the grid. You may only move either right or down at each step.

If the input is not a valid grid (i.e. a list of lists of positive integers) then output None.

The recurrence used in the dynamic programming solution is given by:

[ \text{dp}[i][j] = \max(\text{dp}[i-1][j],; \text{dp}[i][j-1]) + \text{grid}[i][j], \quad \text{for } i,j>0 ]

Implement a program that reads the grid from stdin as a JSON formatted string and outputs the maximum path sum to stdout. If the input grid is invalid, output None.

inputFormat

The input is a single line containing a JSON array that represents a 2D grid. For example:

[[1, 3, 1], [1, 5, 1], [4, 2, 1]]

If the input cannot be parsed as a valid 2D list of positive integers, the program should output None.

outputFormat

Output a single line containing the maximum path sum computed from the grid, or None if the input grid is invalid.

## sample

[[1, 3, 1], [1, 5, 1], [4, 2, 1]]

12