Problem Description

Recently, you inherited a piece of land from your great-great-grandfather. This land is a rectangle with $N$ rows and $M$ columns. You want to continue your great-grandfather’s legacy and start planting two types of plants: wheat and sunflowers.

In each cell of the field, you can plant seeds of one of the two plants. Planting wheat in cell $(i,j)$ earns $A[i][j]$ euros, while planting sunflowers in the same cell $(i,j)$ earns $B[i][j]$ euros.

Unfortunately, you soon discover that if you plant different types of plants in adjacent cells, their roots will get tangled together, and you will need to spend a lot of money to fix it.

Now you urgently want to know: if in every cell you plant only one of the two types of seeds, what is the maximum amount of money you can obtain.

Input Format

The first line contains two integers $N(1 \le N \le 70)$ and $M(1 \le M \le 70)$, representing the number of rows and columns.

The next $N$ lines contain $M$ integers $(1 \le A[i][j] \le 10^5)$.

The next $N$ lines contain $M$ integers $(1 \le B[i][j] \le 10^5)$.

The next $N$ lines contain $M-1$ integers $(1 \le C_1[i][j] \le 10^5)$, representing the loss if different seeds are planted in cells $(i,j)$ and $(i,j+1)$.

The next $N-1$ lines contain $M$ integers $(1 \le C_2[i][j] \le 10^5)$, representing the loss if different seeds are planted in cells $(i,j)$ and $(i+1,j)$.

Output Format

Output one number, the answer.

2 2
1 6
7 1
5 1
1 3
1
1
2 1

16

Hint

Translated by ChatGPT 5