P9276 [AGM 2023 Qualifier] Wheat Field

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.

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 one number, the answer.

Translated by ChatGPT 5