Question
Maximum Coin Path
Tom is walking through a coin field arranged as an n × m grid.
Each cell in the grid contains some coins.
-
Tom starts at the top-left cell
(0, 0). -
He must reach the bottom-right cell
(n-1, m-1). -
At each move, Tom can only go right or down.
Your task is to find the maximum number of coins Tom can collect on his way to the destination.
Input
The first line contains two integers n and m, representing the dimensions of the grid.
The next n lines each contain m space-separated integers, representing the coin values in the grid.
The next n lines each contain m space-separated integers, representing the coin values in the grid.
Output
Return a single integer, representing the maximum number of coins Tim can collect.
Example
Input
3 3
1 3 0
2 5 1
0 6 0
Output
15
Explanation
Maximum number of coins can be collected by traversing the path through the following cells:
(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)
The total coins collected along this path are: 1 + 3 + 5 + 6 = 15
Input
2 2
1 2
3 4
Output
8
Explanation
Maximum number of coins can be collected by traversing the path through the following cells:
(0, 0) → (1, 0) → (1, 1)
The total coins collected along this path are: 1 + 3 + 4 = 8
3 3
1 3 0
2 5 1
0 6 0
Output
15
Explanation
Maximum number of coins can be collected by traversing the path through the following cells:
(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)
The total coins collected along this path are: 1 + 3 + 5 + 6 = 15
Input
2 2
1 2
3 4
Output
8
Explanation
Maximum number of coins can be collected by traversing the path through the following cells:
(0, 0) → (1, 0) → (1, 1)
The total coins collected along this path are: 1 + 3 + 4 = 8