Recently, you have inherited a field from your great-great-grandfather, The Great Farmer. The field can be viewed as a rectangular matrix, with $$$n$$$ rows and $$$m$$$ columns. You want to continue the legacy of your great-great-grandfather, and start cultivating the field with two types of plants: wheat and sunflower.
You soon realize you can turn this into a business: in each cell of the field, you can put one of the two seeds. Planting wheat at cell $$$(i, j)$$$ earns you $$$A[i][j]$$$ euros, while planting sunflower at the same cell $$$(i, j)$$$ earns you $$$B[i][j]$$$ euros.
Unfortunately, you soon observe that if you plant different types of plants in adjacent cells, their roots will tangle up and it will cost you an amount of money to fix.
You are now eager to find what is the maximum amount of money you can receive if you optimally plant exactly one of the two seeds in each cell.
The first line of the input will contain two integers $$$N$$$ ($$$1 \leq N \leq 70$$$) and $$$M$$$ ($$$1\leq M \leq 70$$$), representing the number of rows and columns of the field.
The next $$$N$$$ lines will contain $$$M$$$ integers ($$$1 \leq A[i][j] \leq 10^5$$$), denoting the reward of planting wheat in cell $$$(i, j)$$$.
The next $$$N$$$ lines will contain $$$M$$$ integers ($$$1 \leq B[i][j] \leq 10^5$$$), denoting the reward of planting sunflower in cell $$$(i, j)$$$.
The next $$$N$$$ lines will contain $$$M - 1$$$ integers ($$$1 \leq C_1[i][j] \leq 10^5$$$), denoting the penalty of planting different seeds in cells $$$(i, j)$$$ and $$$(i, j + 1)$$$.
The next $$$N - 1$$$ lines will contain $$$M$$$ integers ($$$1 \leq C_2[i][j] \leq 10^5$$$), denoting the penalty of planting different seeds in cells $$$(i, j)$$$ and $$$(i + 1, j)$$$.
The output file will contain a single number, the maximum amount of money you can earn.
2 2 1 6 7 1 5 1 1 3 1 1 2 1
16
| AGM 2023 Qualification Round |
|---|
| Finished |
