Description

Kids now love "Pleasant Goat and Big Big Wolf" (Xi Yangyang yu Hui Tailang). Although Big Big Wolf fails to catch goats, he is quite good at catching rabbits. The rabbits here are rather slow-witted and have only two burrows. As the Wolf King, you face a terrain shaped like a grid:

The upper-left point is $(1,1)$, and the lower-right point is $(N,M)$ (in the figure, $N=3$, $M=4$). There are three types of roads:

1. $(x,y)\rightleftharpoons(x+1,y)$
2. $(x,y)\rightleftharpoons(x,y+1)$
3. $(x,y)\rightleftharpoons(x+1,y+1)$

The weight on a road indicates the maximum number of rabbits that can pass through that road; roads are undirected. The upper-left and lower-right corners are the two burrows of the rabbits. Initially, all rabbits gather in the upper-left burrow at $(1,1)$, and now they want to run to the lower-right burrow at $(N,M)$. The Wolf King starts to ambush these rabbits. To be safe, if the maximum number of rabbits that can pass through a road is $K$, the Wolf King needs to assign the same number of $K$ wolves to completely block this road. You need to help the Wolf King plan an ambush so that, while ensuring all rabbits are captured, the number of participating wolves is minimized, since the wolves still need to trouble Pleasant Goat later.

Input Format

The first line contains two integers $N, M$, indicating the size of the grid.

Then the input consists of three parts.

• Part 1: $N$ lines, each containing $M-1$ numbers, representing the weights of horizontal roads.
• Part 2: $N-1$ lines, each containing $M$ numbers, representing the weights of vertical roads.
• Part 3: $N-1$ lines, each containing $M-1$ numbers, representing the weights of diagonal roads.

Output Format

Output a single integer, the minimum number of wolves needed for the ambush.

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

14

Hint

Constraints

For all test points, it is guaranteed that $3 \leq N, M \leq 1000$, and all road weights are positive integers not exceeding $10^6$.

Translated by ChatGPT 5