Treasure Path

In this problem, you are given a grid of integers representing treasures. You start at the top-left cell and move to the bottom-right cell, only moving right or down. Your task is to compute the maximum amount of treasure you can collect along the path. The dynamic programming recurrence is given by (dp[i][j]=\max(dp[i-1][j], dp[i][j-1]) + grid[i][j]). If the grid is invalid (empty, has zero rows or columns, or contains non-integer values), output "Invalid grid dimensions".

inputFormat

The input is read from standard input (stdin). The first line contains two integers (m) and (n) representing the number of rows and columns respectively. This is followed by (m) lines, each containing (n) integers separated by spaces. A valid grid must satisfy (m > 0), (n > 0) and all cells must be integers.

outputFormat

Output the maximum treasure sum obtainable from the top-left to the bottom-right cell if the grid is valid. Otherwise, output "Invalid grid dimensions". The result should be printed to standard output (stdout).## sample

3 3
1 3 1
1 5 1
4 2 1

12