题目描述

牛哥有 $n×m$ 个砖块排布成 $n$ 行 $m$ 列的矩阵，我们使用 (i,j)表示矩阵中从上往下数第 $i$ 行和从左往右数第 $j$ 列的砖块。如下左图就是一个 $6$ 行 $6$ 列的矩阵。有的砖块能被敲碎，为了便于辨认，我们使用灰色绘制它们；有的砖块不能被敲碎，我们使用蓝色斜线绘制它们。如下右图所示，第 $3$ 行第 $2$ 列的砖块 ($3$,$2$) 是灰色的，能被敲碎，使用一个叉代表其被敲碎了。

对于使用蓝色斜线绘制的砖块，它们是一体的，牛可乐定义“蓝色极大连通块”为最大化上下左右（即四连通）连接的蓝色砖块个数、且不包含灰色砖块的连通块，例如，在上图中，唯一的“蓝色极大连通块”包含 $4$ 个蓝色砖块，分别为 ($3$,$3$),($3$,$4$),($4$,$3$),($4$,$4$)。 与真实生活一样，如果一个“蓝色极大连通块”的任意一个砖块都不与灰色砖块存在共边，则认为这个“蓝色极大连通块”完好地从原砖块掉落。例如，在上图中，要使得“蓝色极大连通块”掉落，至少需要敲碎八块砖块，如下图所示 ​

特别地，对于位于边界上的“蓝色极大连通块”，不需要关注悬空的那些。例如，在下左图中，唯一的“蓝色极大连通块”包含 $2$ 个蓝色砖块，分别为 ($1$,$1$),($1$,$2$)，其位于边界上，要使得它掉落，至少需要敲碎 $3$ 块砖块，如下图所示。 现在，对于牛可乐给你的砖块矩阵，你需要帮助他分离出任意一块“蓝色极大连通块”，计算最少需要敲碎的灰色砖块个数

输入格式

第一行输入两个正整数n,m ($1<=n$,m<=$500$)代表砖块矩阵的行数和列数。 接下来 $n$ 行，第 $i$ 行输入一个长度为 $m$、仅有字符'$0$'和'$1$'组成的字符串s~i,$1$~s~i,$2$~...s~i,m~，其中s~ij~='$0$' 代表(i,j)是灰色砖块s~ij~='$1$'代表(i,j)是蓝色砖块

输出格式

输出一个整数，代表最少需要敲碎的灰色砖块个数。

样例 1

样例输入 1

6 6
000000
000000
001100
001100
000000
000000

样例输出 1

8

样例 2

样例输入 2

2 3
110
000

样例输出 2

3

样例 3

样例输入 3

2 2
11
11

样例输出 3

0

样例 4

样例输入 4

4 5
10000
00111
11000
00000

样例输出 4

2

样例 5

样例输入 5

3 3
111
101
111

样例输出 5

1