Taco: Maximum Path Sum

You are given a grid of integers with m rows and n columns. Your task is to compute the maximum sum of numbers collected starting from the top-left corner and ending at the bottom-right corner of the grid. At each step, you can move either right or down.

The problem can be mathematically expressed as finding a path that maximizes the following sum:

$$\text{maxPathSum} = \max_{\text{path}} \sum_{(i,j) \in \text{path}} a_{i,j}, $$

where the path starts at (0, 0) and ends at (m-1, n-1). Only rightward and downward moves are allowed.

Input: The first line contains two integers m and n. The following m lines each contain n space-separated integers representing the grid.

Output: Output a single integer denoting the maximum path sum.

inputFormat

Input is read from standard input (stdin). The first line contains two integers m and n — the number of rows and columns of the grid respectively. Each of the next m lines contains n space-separated integers representing the grid.

Example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum of a path from the top-left corner to the bottom-right corner, moving only right or down.

Example:

12

## sample

3 3
1 3 1
1 5 1
4 2 1

12