There is a checkered field of size NxM. Each cell can contain either reagent A or B, or nothing - 0. During a turn, you can put reagent A into some cell, and the transformation of the substance proceeds according to the following rule: 0+A->A, A+A-> ;B, B+A->0. In this case, as a result of the last reaction, an explosion occurs, and a portion of reagent A falls into neighboring non-empty cells on the cardinal points (if any). Points per move = number of explosions minus 1. Points for individual moves are summed up. It is required to clear the field and at the same time score the maximum number of points.
Input
On the first line, N and M are entered (1 <= N, M <= 3). Next come N lines of M characters each from the alphabet (0, A, B) - description of the field.
Output
Print a single number - the maximum number of points you can score.
Comment to the second example: not a single explosion occurred during the first move, points=0-1=-1; for the second move there was one explosion and the field was cleared, points=1-1=0; total points: 0+(-1)=-1
|
Enter |
Output |
1 1
0 |
0 |
1 1
A |
-1 |