Problem Description

JOI is at the beach with his family. After swimming, he decides to build a sandcastle on the beach. After playing with it for a while, he gets bored and goes back to swimming.

The sandcastle is within a rectangular area on the beach, which is divided into a grid. Each cell in this grid is either part of the sandcastle (referred to as a "castle cell") or not (referred to as a "open cell"). Each castle cell has a "strength" value, which is an integer between 1 and 9. The outer edge of the rectangular area, i.e., the cells that are adjacent to the outside, do not contain any castle cells.

As the tide comes in, waves start to hit the rectangular area. Each wave causes castle cells that meet the following condition to collapse and turn into open cells:

Condition: The number of open cells in the surrounding 8 cells (north, south, east, west, northeast, northwest, southeast, southwest) is greater than or equal to the strength value of the castle cell.

After a wave recedes, another wave soon follows. After many waves, the castle will either completely collapse or only the strongest parts will remain, such that no castle cells collapse with the incoming waves. Determine the number of waves that cause at least one castle cell to collapse.

Input Format

The input consists of \(1 + H\) lines.

The first line contains two integers \(H, W\) (\(2 \leq H \leq 1000\), \(2 \leq W \leq 1000\)), indicating that the rectangular area is divided into \(H \times W\) cells. The vertical direction is north-south, and the horizontal direction is east-west.

The next \(H\) lines each contain a string of \(W\) characters, representing the state of the rectangular area before the first wave arrives. The \(i\)-th line from the top and the \(j\)-th character from the left (\(1 \leq i \leq H\), \(1 \leq j \leq W\)) is a . if the cell is an open cell. If it is a castle cell, it is one of 1, 2, ..., 9, representing the strength of that cell.

The outer edge of the rectangular area is all open cells. That is, for all inputs, the characters in the first or last row, and the first or last character in each row, are all ..

In input 1, \(H \leq 50\) and \(W \leq 50\).

Output Format

Output the number of waves that cause at least one castle cell to collapse on a single line.

Sample Input and Output

Sample Input #1

5 6
......
.939..
.3428.
.9393.
......

Sample Output #1

3

Sample Input #2

10 10
..........
.99999999.
.9.323239.
.91444449.
.91444449.
.91444449.
.91444449.
.91232329.
.99999999.
..........

Sample Output #2

35

Notes/Hints

Sample Explanation 1

In the first sample, the first wave causes all strength 3 castle cells to collapse, resulting in:

......
.9.9..
..428.
.9.9..
......

The second wave causes the strength 2 castle cell to collapse:

......
.9.9..
..4.8.
.9.9..
......

The third wave causes the strength 4 castle cell to collapse:

......
.9.9..
....8.
.9.9..
......

No more castle cells collapse after this. Therefore, the answer is 3.

见题面 Input 部分

见题面 Output 部分