409548: GYM103627 L Curly Racetrack

You are creating a new KartRider racetrack. The racetrack is a $$$H \times W$$$ rectangular board. Each cell of the board is either empty, or contains a tile which is described in the picture below.

Note that each of the tiles can be rotated, and all except one have roads going out of the tile. We denote the fourth type of tile (highlighted in blue color) as a curly tile.

In a valid KartRider racetrack, every cell should contain a tile, and there should be no dead-ends over the roads in the tile. In other words, each road going out of the tile should be connected to a road on the neighboring tile. Also, the road should not face outside the board.

Currently, there are some curly tiles already placed on the board. You can place zero or more curly tiles on the board and submit the racetrack. Then, the administrator will try to fill all empty cells with tiles (not necessarily curly) with their best effort, so that it becomes a valid KartRider racetrack. Note that you can only place the curly tiles, and you should not remove, replace, or rotate the curly tiles already placed in the board.

Additionally, for some cells, you can not place the tiles, and for some cells, you must place the curly tiles.

Please find the maximum possible number of curly tiles you can place in the racetrack so that the administrator can fill the remaining cells to create a valid KartRider racetrack. You should report the total number of curly tiles in the racetrack, not the number of curly tiles you have newly added. If there is no way to create a valid KartRider racetrack, print $$$-1$$$.

The first line contains two integers $$$H$$$ and $$$W$$$ denoting the size of the board. ($$$1 \le H, W \le 100$$$)

The next $$$H$$$ lines contain the information about the board. Each line consists of $$$W$$$ characters, denoting the following:

• "1": Curly tile containing road connecting upper and left cells,
• "2": Curly tile containing road connecting lower and left cells,
• "3": Curly tile containing road connecting upper and right cells,
• "4": Curly tile containing road connecting lower and right cells,
• "o": Empty cell where curly tile must be placed,
• "x": Empty cell where you can not place the tile,
• ".": Empty cell which has no restrictions.

Output the maximum possible number of curly tiles you can place on the racetrack so that the administrator can fill the remaining cells to create a valid KartRider racetrack. You should report the total number of curly tiles on the racetrack, not the number of curly tiles you have newly added. If there is no way to create a valid KartRider racetrack, print $$$-1$$$.

4 5
4...x
.2..2
.o1x.
3..3o

12

2 3
4o2
3x1

-1

The following image illustrates the original state of the board in the first sample input.

The following image illustrates the final state of the board in the optimal solution. Tiles placed by the administrators are highlighted in yellow.