题目描述

农夫有一个 $n \times m$ 大小的农场，农场的四周有墙把农场跟外面隔离开，同时农场里也有一些隔离墙，其余的是空地。

农夫想养一些公羊，但是公羊好斗，而且公羊在农场里会"上下左右"四处走动（但不能穿过墙），两只公羊不能见面。为了让公羊不受伤，农夫想知道他的农场最多能养几只公羊。

农场用 0 表示空地，1 表示墙。

第一行两个整数 $n$ 和 $m$（$1 \le n,m \le 1000$），表示农场大小是 $n \times m$。

接下来 $n$ 行，每行 $m$ 个整数（0 或 1），用空格隔开。

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

样例

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

3

说明/提示

对于所有数据，$1 \le n, m \le 1000$。