Mosaic

Consider a mosaic of black tiles laid on a rectangular grid with a white background. Each cell of the grid holds one black square tile, one black triangular tile, or nothing at all, in which case the cell stays white. A triangular tile is the right isosceles triangle obtained by cutting a cell along one of its diagonals, and it comes in four orientations, one for each corner where the right angle sits.

Figure 1: an example of a mosaic

Figure 2: the four orientations of a triangular tile

Every mosaic is built so that each region left white is a rectangle. Such a rectangle is either aligned with the grid or turned by 45 degrees.

The artist starts by placing all of the black squares, and assistants fill in the remaining black triangles. So that the assistants reproduce the intended design, the artist writes a number on some of the black squares giving the count of black triangles that share an edge with that square. A triangle in a neighbouring cell shares an edge with the square only when it covers the whole common edge of the two cells. A black square without a number may have any number of triangles sharing an edge with it. The artist writes down enough numbers to pin the mosaic to a single design.

Figure 3: a starting configuration that determines the mosaic of Figure 1 uniquely

Given a starting configuration, determine how many triangles the finished mosaic uses.

Mosaics of this kind come from the Nikoli puzzle Shakashaka.

The input consists of a single test case.

The first line contains the width $W$ and the height $H$ of the mosaic ($1 \le W \le 24$, $1 \le H \le 18$).

Each of the next $H$ lines contains $W$ characters. The characters 0, 1, 2, 3 and 4 mark a black square whose number of edge-sharing black triangles is fixed to that digit, and the character * marks a black square with no such constraint. Every remaining position is ., and must be left empty or covered by a single black triangle.

The input always determines exactly one valid mosaic.

Print the number of triangles used in the mosaic.