This is a maximum bipartite matching problem. Don't let anyone convince you this is dynamic programming.

See https://codeforces.com/contest/1404/problem/E.

We solve the task using dynamic programming. The state is the row and column of the current square, and a bitmask that represents what happened on the last ~m~ squares, i.e. the current square, squares that are in the current row and on the left side, and squares in the previous row that are on the right side of the current square.

The current square is colored red, and other squares that are represented in the bitmask are colored blue. Let bit ~0~ mean that the square is covered by a horizontal piece of tape, and bit ~1~ mean that it is covered by a vertical one. If we want to use a horizontal piece to cover the current square, then if the square on the left is also covered by a horizontal piece, we can just continue using that piece, otherwise we need a new piece of tape. Similar thing holds if we want to use a vertical piece.

The transitions are:

• if bits corresponding to the current and the left square are both ~0~:

  $$\displaystyle dp[i][j][mask] = \min(dp[i][j-1][mask], dp[i][j-1][mask \oplus 2^j])$$

• if the bit corresponding to the current square is ~0~, and the left square doesn't exist or its bit is equal to ~1~:

  $$\displaystyle dp[i][j][mask] = \min(dp[i][j-1][mask], dp[i][j-1][mask \oplus 2^j])+1$$

  and if ~j~ equals ~0~, we do the transition using ~dp[i-1][m-1]~.

• if the bit corresponding to the current square is ~1~:

  $$\displaystyle dp[i][j][mask] = \min(dp[i][j-1][mask], dp[i][j-1][mask \oplus 2^j]+1)$$

We also need to take care of the open squares, we can't continue to use a piece that covers one of them. The complexity is ~\mathcal O(nm \times 2^m)~.