Description

有一个农夫有个n×m大小的农场，农场的四周有墙把农场跟外面隔离开，同时农场里也一些隔离墙，其余的是空地. 农夫想养一些公羊，但是公羊好斗，而且公羊在农场里会”上下左右"四处走动（但不能穿过墙），两只公羊不能见面（见面就会顶角受伤），为了不让公羊受伤，农夫想知道他的 农场最多能养几只公羊？ 为了方便起见，农场的描述用0表示空地，1表示墙。

Input

第一行输入n和m，表示农场大小是n×m（1≤n,m≤1000） 接下来是一个n×m的矩阵，矩阵里每个值是0或者1

Output

一行，一个整数，表示农夫能养的公羊数量.

Samples

4 5
10111
10101
11110
10000

3

Limitation

1s, 1024KiB for each test case.