Maximizing T-Tetromino Coverage Sum

You are given a grid with n rows and m columns. Each cell of the grid contains an integer value. In addition, some cells are marked as special cells. A T-tetromino is a piece covering exactly 4 cells in a T-shape. Its center cell is marked with a ×. There are four possible orientations of a T-tetromino:

• Up: covers cells at offsets \( (0,0), (0,-1), (0,1), (-1,0) \).
• Down: covers cells at offsets \( (0,0), (0,-1), (0,1), (1,0) \).
• Left: covers cells at offsets \( (0,0), (-1,0), (1,0), (0,-1) \).
• Right: covers cells at offsets \( (0,0), (-1,0), (1,0), (0,1) \).

Manca has drawn the grid and marked some cells as special. She intends to place exactly as many T-tetrominoes as there are special cells. Moreover, each T-tetromino must have its center placed on a special cell. The T-tetrominoes must:

1. Be entirely inside the grid.
2. Not overlap with each other.

Each tetromino covers 4 cells, and the goal is to choose an orientation for each special cell so that the tetromino placements are valid and the sum of the grid values covered by the tetrominoes is maximized.

If it is impossible to place tetrominoes for all special cells, output No. Otherwise, output the maximum sum.

inputFormat

The first line contains two integers n and m (the number of rows and columns respectively).

The next n lines each contain m integers representing the grid values.

The following n lines each contain m integers (either 0 or 1), where 1 indicates a special cell and 0 indicates a normal cell.

outputFormat

If there is no valid placement for all T-tetrominoes, output No (without quotes). Otherwise, output a single integer — the maximum sum of the grid values covered by the tetrominoes.

sample

3 3
1 2 3
4 5 6
7 8 9
0 1 0
0 0 0
0 1 0

No