Description

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?

Input Format

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 Format

Output the maximum number of posters that can be placed.

6 6
0 0 0 1 0 0 
0 1 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 1 0 0

3

Hint

The testdata guarantees that $1\leq n\leq 150$, $1\leq m\leq 10$.

Translated by ChatGPT 5