Captain Q's Treasure

Time limit3sMemory limit128 MB

Summary

Given a grid with at most 15 digit cells, each stating how many chests lie in its 3x3 neighborhood, find the minimum number of chests consistent with all digits.

Level: Hard8 of 10
Topics: Backtracking, Brute force, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

You have obtained an old map that turns out to have been drawn by the notorious pirate “Captain Q”. It marks the locations of many treasure chests buried on an island.

The map is divided into square cells. Each cell either shows a single digit or shows no digit. A digit on a cell tells how many chests are buried in the 9 cells of its neighborhood (the cell itself together with its 8 surrounding cells). You may assume that each cell holds at most one chest.

Even with the map you cannot tell exactly which cells hold chests, and you do not even know the total number of chests buried on the island. You can, however, compute the minimum possible number of chests. Your task is to write a program that computes this minimum.

Input

The input is a sequence of datasets. Each dataset has the following format.

h w
map

The first line of a dataset contains two positive integers $h$ and $w$ : $h$ is the height of the map and $w$ is its width. You may assume $1 \le h \le 15$ and $1 \le w \le 15$ .

The next $h$ lines describe the map. Each line has $w$ characters and corresponds to one horizontal strip of the map. Each character encodes the state of a cell as follows.

. : the cell is not part of the island (water); no chest is here.
* : the cell is part of the island, and the number of chests in its 9 neighbors is unknown.
0–9 : the cell is part of the island, and the digit is the number of chests in its 9 neighbors.

You may assume that the map is never self-contradicting; that is, at least one valid arrangement of chests exists. You may also assume that the number of cells carrying a digit is at least one and at most 15.

A line containing two zeros marks the end of the input.

Output

For each dataset, print a line containing the minimum number of chests. The output must not contain any other character.

Examples8

Example 1

Input

5 6
*2.2**
..*...
..2...
..*...
*2.2**
6 5
.*2*.
..*..
..*..
..2..
..*..
.*2*.
5 6
.1111.
**...*
33....
**...0
.*2**.
6 9
....1....
...1.1...
....1....
.1..*..1.
1.1***1.1
.1..*..1.
9 9
*********
*4*4*4*4*
*********
*4*4*4*4*
*********
*4*4*4*4*
*********
*4*4*4***
*********
0 0

Expected output

Example 2
Input
```
1 1
0
0 0
```
Expected output
```
0
```
Example 3
Input
```
1 1
1
0 0
```
Expected output
```
1
```
Example 4
Input
```
1 3
1*1
0 0
```
Expected output
```
1
```
Example 5
Input
```
3 3
***
*4*
***
0 0
```
Expected output
```
4
```
Example 6
Input
```
1 7
1.*.1.*
0 0
```
Expected output
```
2
```
Example 7
Input
```
2 5
*2*2*
.....
0 0
```
Expected output
```
3
```
Example 8
Input
```
1 1
0
1 1
1
1 3
1*1
0 0
```
Expected output
```
0
1
1
```