Gugle is one of the most powerful information technology companies. Now it has another new office whose layout looks like an N × M grids. Some cells in the grids are occupied by chairs; some cells are occupied by computers; while others are empty.
Engineers in Gugle are all hard-working. Every one asks for two nearby computers (sharing a common edge with his chair) so he can operates both simultaneously at work. Futher more, no one can operate two computers in opposite directions at the same time, so the both computers must forms a right angle.
For eaxample, when an engineer sits at (x, y), he can't operate computers located at (x+1, y) and (x-1, y) simultaneously. Instead he may operate computers at (x-1, y) and (x, y-1).
Gugle wants to know many engineers this office can hold without moving the computers and chairs.
3 4 2 2 1 2 0 1 2 2 2 2 2 1
2