题目描述

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

输入格式

第一行输入n和m，表示农场大小是nxm(1≤n,m≤1000)。接下来是一个nxm的矩阵,矩阵里每个值是0或者1。行内数之间用空格隔开。

输出格式

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

样例

输入样例 1

4 5
1 0 1 1 1
1 0 1 0 1
1 1 1 1 0
1 0 0 0 0

输出样例 1

3

输入样例 2

3 3
0 0 0
0 0 0
0 0 0

输出样例 2

1

输入样例 3

5 5
0 0 1 0 0
0 1 1 1 0
0 0 0 0 0
1 1 0 1 1
0 0 0 0 0

输出样例 3

1