P1924 Pasting Posters

There is a wall of size $n\times m$ with several holes on it. You need to paste posters on the wall. Each poster is a $2\times 3$ rectangle, with each side parallel or perpendicular to the wall’s edges. A poster can be placed horizontally or vertically, but no poster may cover any hole. What is the maximum number of posters that can be placed on this wall?

The first line contains $2$ integers $n$ and $m$, indicating that the wall size is $n\times m$. The next $n$ lines each contain $m$ integers $0$ or $1$. A $1$ indicates that position has a hole, and a $0$ indicates no hole.

Output the maximum number of posters that can be placed.

The testdata guarantees that $1\leq n\leq 150$, $1\leq m\leq 10$. Translated by ChatGPT 5