Maximum Sum Path

Task

Given a grid of integers $A$ consisting of $N$ rows and $M$ columns, where each of its cells has a color and a number written on it.

Find the maximum sum of numbers on the cells of a path that goes only right and down, such that its starting and ending cells have the same color.

Input data

The input file consists of:

• a line containing integers $N$, $M$.
• $N$ lines, the $i$-th of which consisting of the $M$ integers $A_{i,0}, \, \ldots, \, A_{i,M-1}$, where $A_{i,j}$ is the integer in the cell $(i, j)$.
• $N$ lines, the $i$-th of which consisting of the $M$ integers $C_{i,0}, \, \ldots, \, C_{i,M-1}$, where $C_{i,j}$ is the color of the cell $(i, j)$.

Output data

Output a single line containing a single integer -- the answer to the problem.

Constraints and clarifications

• $1 \le N \le 500$.
• $1 \le M \le 500$.
• $-10^9 \le A_{i,j} \le 10^9$ for each $i=0\ldots N-1$ and $j=0\ldots M-1$.
• $1 \le C_{i,j} \le 500$ for each $i=0\ldots N-1$ and $j=0\ldots M-1$.

Example 1

stdin

3 3
1 1 2
0 -1 -4
1 5 1
3 2 3
4 5 6
2 3 1

stdout

7

Explanation

In the first example, the maximum sum path goes through the cells $(0, 0)$, $(1, 0)$, $(2, 0)$, $(2, 1)$.

Notice that it's possible to achieve a greater sum by continuing to the cell $(2, 2)$,
but that path shouldn't be considered because its starting cell $(0, 0)$ has a different color form its ending cell $(2, 2)$.

Example 2

stdin

2 2
0 -1
1 1
1 1
1 1

stdout

2

Explanation

In the second example, the maximum sum path goes through the cells $(1, 0)$ and $(1, 1)$.