Migrated from Lutece 2182 扫广场

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

eom是jjjj手下的清洁工，今天他又被叫去给jjjj的广场扫垃圾。广场可以被视作一个$n*m$的矩形地区，在其中一些块会有垃圾挡住行人的通行，于是jjjj叫eom要把一些垃圾清除使得干净的地区都能互相连通。偷懒的eom想要知道他至少要打扫多少块地区才能达到jjjj的要求？

Input

第一行为两个整数$n$和$m$，表示城市有$n$行$m$列。

接下来$n$行每行有$m$个字符，'1'表示有垃圾，'0'表示空地。

Output

输出一个整数表示最少需要打扫多少块地上的垃圾。

Samples

5 3
000
001
110
000
010

1

Constraints

$nm\le 80$

Note

样例中打扫区域(2,3),(3,1)或(3,2)都能使空地联通

Resources

2019 UESTC ACM Training for Dynamic Programming