MegaDamas

MegaDamas is a board game for two players, very similar to the well-known game of checkers (Damas). The board is rectangular, with $N$ rows and $M$ columns of small squares arranged in an $N \times M$ grid. The small squares are colored alternately with a light color and a dark color, in the usual pattern of a checkers board. The dark squares are called "houses". Note, however, that for readability the diagrams below draw houses as white squares.

At the start of the game, each player has a certain number of pieces, placed on the houses closest to the edge of the board that the player chooses. The players choose opposite edges. During the game, pieces can occupy only the houses of the board.

One of the moves of the game is to "capture" an opponent's piece by jumping over it diagonally to the adjacent house beyond it, and that house must be empty. The opponent's piece is then removed from the board. The three houses involved in a capture (the starting house of your piece, the house holding the opponent's piece, and the empty house where your piece lands) must lie on one diagonal and be diagonally adjacent, as in the diagram below.

In MegaDamas a piece can capture opponent pieces by jumping diagonally forward or backward (in most existing variations of checkers, a piece can capture only by jumping forward). You can also make a multiple capture with a single piece, jumping over opponent pieces into empty houses one jump after another. In a multiple capture your piece can change direction, jumping first in one direction and then in another. You can capture only one piece per jump, but you can capture several pieces with consecutive jumps. You cannot jump over one of your own pieces, and you cannot jump over the same opponent piece more than once. The house that the moving piece leaves becomes empty.

You are given the dimensions of the board and a description of the current state of a game. It is your turn, and you must determine the maximum number of your opponent's pieces that can be captured in one capture move. If no capture is possible, the answer is 0.

The input contains several test cases. The first line of a test case contains two integers $N$ and $M$, the number of rows and the number of columns of the board ($3 \le N \le 20$, $3 \le M \le 20$, $N \times M \le 200$). The leftmost square of the board on the edge closest to you is a house. So in the $i$-th row counted from your edge (starting from 1), the houses are columns 1, 3, 5, ... when $i$ is odd and columns 2, 4, 6, ... when $i$ is even.

The second line contains the description of the game state. It consists of $\lceil (N \times M)/2 \rceil$ integers separated by single spaces, one for each house of the board. The houses are numbered from 1 to $\lceil (N \times M)/2 \rceil$, row by row from the edge closest to you to the edge closest to your opponent, and from left to right within a row. In the game state, 0 is an empty house, 1 is a house with one of your pieces, and 2 is a house with one of your opponent's pieces. Each player has at most $\lfloor (N \times M)/4 \rfloor$ pieces on the board.

The end of input is marked by a line with $N = M = 0$.

Figure 1: Numbering of the houses on (a) an $8 \times 8$ board and (b) a $5 \times 3$ board.

For each test case, print one line with one integer: the largest number of your opponent's pieces that can be captured in one move.