Minimum Removal to Avoid Forbidden Block Pattern

Old C, a programmer with a penchant for playing block games on his computer, faces a peculiar dilemma. The game is played on an R × C grid where each cell may contain a block. However, certain pairs of adjacent cells in the grid are connected by special edges whose positions are determined by a specific periodic pattern. In particular, the horizontal special edges are defined as follows:

• For any row with an odd index (1-indexed), a special horizontal edge exists between the j-th cell and the (j+1)-th cell if j ≡ 1 (mod 4).
• For any row with an even index, a special horizontal edge exists between the j-th cell and the (j+1)-th cell if j ≡ 3 (mod 4).

Similarly, the vertical special edges are defined with a period of 2 in the vertical direction. For our purposes, we define them as:

• For any column with an odd index, a special vertical edge exists between the i-th cell and the (i+1)-th cell if i is odd (1-indexed).
• For any column with an even index, a special vertical edge exists between the i-th cell and the (i+1)-th cell if i is even (1-indexed).

Old C despises a particular shape – a configuration of 4 blocks forming a 2×2 square with a distinguished special edge. Concretely, if there is a 2×2 subgrid whose cells are all filled with blocks and which aligns with the special edge pattern in one of the two ways listed below, then that configuration is forbidden (and will cause Old C to quit):

1. Horizontal orientation: Let the top row of the 2×2 subgrid be in row i (1-indexed). If
   • i is odd and the special horizontal edge exists between the first two cells of that row (i.e. the left cell is in a column j with j ≡ 1 (mod 4)),
   • or i is even and the special horizontal edge exists between the two cells (i.e. the left cell is in a column j with j ≡ 3 (mod 4)),
   then the subgrid is forbidden if all its 4 cells have blocks.
2. Vertical orientation: Similarly, if the left column of the 2×2 subgrid is column j (1-indexed) and
   • j is odd and the special vertical edge exists between the top two cells of that column (i.e. the top cell is in a row with an odd index),
   • or j is even and the special vertical edge exists (i.e. the top cell is in a row with an even index),
   then the subgrid is forbidden if all its 4 cells have blocks.

Old C’s current grid already has some blocks in place. In order to avoid triggering his despair, he wishes to remove a set of blocks (each removal incurring a specified cost) so that no forbidden pattern appears anywhere on the grid (note that the pattern is considered under all rotations and reflections, but a 2×2 square is invariant under these transformations). More formally, for every 2×2 subgrid that aligns with the special edge pattern as described above, at least one block must be removed.

Your task is to help him determine the minimum total cost required to achieve this goal.

Input/Output Format: See the sections below.

inputFormat

The first line contains two integers R and C — the number of rows and columns of the grid.

The next R lines each contain C integers. The j-th integer in the i-th line is either 1 or 0, indicating whether the cell originally contains a block (1 means a block is present, and 0 means it is empty).

The following R lines each contain C integers. For a cell that originally contains a block (value 1 in the previous section), the corresponding integer indicates the cost (in coins) to remove that block. For cells with no block, the cost will be 0 (or can be ignored).

You may assume that R and C are small enough (for example, R, C ≤ 10) to allow a solution based on dynamic programming with bitmasking.

outputFormat

Output a single integer, the minimum total cost required to remove blocks so that there is no forbidden 2×2 configuration as described.

sample

2 4
1 1 1 1
1 1 1 1
1 2 3 4
4 3 2 1

2