Rolling-Dice Puzzle

문제

[이미지 1]Sarina and her brother, Soroush, are playing the rolling-dice game. The game is played on an $n\times mn\; \backslash times\; m$ board. Initially, Soroush places a standard dice in one of the cells. It is place in a way that the number $66$ is on the upper face, the number $44$ is on the north face, and the number $22$ is on the west face. In a standard dice, $66$ is on the opposite side of $11$, $22$ is on the opposite side of $55$, and $33$ is on the opposite side of $44$. Additionally, he selects some of the cells and writes arbitrary integers numbers from $11$ to $66$ in them.

After that, Sarina have to move the dice on the board by rolling it multiple times. The act of rolling is defined as follows: Suppose two adjacent cells $AA$ and $BB$ share an edge $ee$ and the dice is on the cell $AA$; The dice can be rolled around its edge incident to $ee$ and moved from $AA$ to $BB$. For example, consider the starting position of the dice. If the dice is rolled around the east, west, north, and south edges, the number appearing on the top face after rolling will be $22$, $55$, $33$, and $44$, respectively.

Whenever Sarina moves the dice to a a cell with a number in it in such a way that the number on the upper face of the dice matches the number in that cell, she gets a point. Note that Sarina can get a point from each cell at most one. The game is not that simple! There are obstacles in some of the cells and it is not possible to move the dice to the cells with an obstacle in it. Your task is to find out the maximum points that Sarina can get.

입력

The first line of input contains two integers $nn$ and $mm$ ($1\le n,m\le 1001\; \backslash le\; n,\; m\; \backslash le\; 100$), indicating the number of rows and columns of the board, respectively. Each of the next n lines contain m characters, describing the board. Empty cells are represented by “.” and obstacles are represented by “x”. The starting position of the dice is represented by “s” and the selected cells are represented by the integers written in them (from $11$ to $66$). It is guaranteed that there is only one “s” in the input.

출력

Output a line containing the maximum points Sarina can get.