Minimum Wolf Deployment

You are given a grid with dimensions \(N \times M\) where the cells are indexed from \((1,1)\) at the top-left to \((N,M)\) at the bottom-right.

There are three types of bidirectional roads connecting adjacent cells:

1. Between \((x,y)\) and \((x+1,y)\) for \(1 \le x < N, 1 \le y \le M\).
2. Between \((x,y)\) and \((x,y+1)\) for \(1 \le x \le N, 1 \le y < M\).
3. Between \((x,y)\) and \((x+1,y+1)\) for \(1 \le x < N, 1 \le y < M\).

Each road has a capacity \(K\) (a positive integer) which represents the maximum number of rabbits that can pass through. The rabbits start at the den located at \((1,1)\) and want to escape to the den at \((N,M)\). In order to ambush the rabbits, the wolf king needs to block some roads. To completely block a road with capacity \(K\), exactly \(K\) wolves must be deployed on that road.

Your task is to help the wolf king determine the minimum total number of wolves required so that all paths from \((1,1)\) to \((N,M)\) are blocked. This is equivalent to finding the minimum cut in the grid where each edge (road) has a weight equal to its capacity.

Note: The roads are undirected. For algorithmic purposes, you can treat each undirected road as two directed edges with the same capacity.

inputFormat

The input consists of the following parts:

1. One line with two integers \(N\) and \(M\) representing the number of rows and columns in the grid.
2. \(N-1\) lines, each containing \(M\) integers. The \(i\)-th of these lines contains the capacities for the vertical roads connecting \((i,j)\) and \((i+1,j)\) for \(j=1\) to \(M\).
3. \(N\) lines, each containing \(M-1\) integers. The \(i\)-th of these lines contains the capacities for the horizontal roads connecting \((i,j)\) and \((i,j+1)\) for \(j=1\) to \(M-1\).
4. \(N-1\) lines, each containing \(M-1\) integers. The \(i\)-th of these lines contains the capacities for the diagonal roads connecting \((i,j)\) and \((i+1,j+1)\) for \(j=1\) to \(M-1\).

All numbers are separated by spaces.

outputFormat

Output a single integer which is the minimum number of wolves required to block all paths from the source \((1,1)\) to the sink \((N,M)\).

sample

2 2
3 2
1
4
2

6