Minesweeper

Time limit2sMemory limit128 MB

Summary

Given a Minesweeper board where only border cells are revealed with numbers, determine the maximum number of mines that can be placed in the closed interior cells consistently with the border clues.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Bit manipulation
Solved: No attempts yet

Problem

You are given an N×N Minesweeper board. Some cells contain mines. Every opened non-mine cell shows how many mines are in the 8 neighboring cells around it.

In this problem, every border cell of the board is already open, and every non-border cell is still closed. Closed cells are written as #. Consider the following board.


1	1	1	0	0
2	#	#	#	1
3	#	#	#	1
2	#	#	#	1
1	2	2	1	0

For this board, at most 6 closed cells can contain mines. One possible placement is shown below.


1	1	1	0	0
2	*			1
3	*	*	*	1
2	*	*		1
1	2	2	1	0

Given the board, find the maximum number of closed cells that can contain mines.

Input

The first line contains an integer N (1 ≤ N ≤ 100).

Each of the next N lines contains a string of length N describing the board. Border cells are digits, and every closed non-border cell is written as #.

Output

Print the maximum number of closed cells that can contain mines.

Examples1

Example 1
Input
```
5
11100
2###1
3###1
2###1
12210
```
Expected output
```
6
```