Simon 有一个由 n 行和 m 列组成的矩形桌子。西蒙从 1 开始,从上到下对表格的行进行编号,从左到右,从 1 开始对表格的列进行编号。我们将第 x 行和第 y 列上的单元格表示为一对数字 (x, y)。表格角是单元格:(1, 1)、(n, 1)、(1, m)、(n, m)。
Simon 认为该表中的某些单元格很好。此外,众所周知,桌子的角落是没有好单元格的。
最初,表格的所有单元格都是无色的。西蒙想要为他的表格中的所有单元格着色。一步操作中,他可以选择表格中任意一个好的单元格 (x1, y1)、表格的任意角 (x2, y2) 并对表格中的所有单元格 (p, q) 进行着色,这些单元格满足以下两个不等式:min(x1, x2) ≤ p ≤ max(x1, x2)、min(y1, y2) ≤ q ≤ max(y1, y2)。
帮助西蒙!求为表格的所有单元格着色所需的最少操作数。请注意,您可以对一个单元格进行多次着色。
输入
第一行恰好包含两个整数 n, m (3 ≤ n, m ≤ 50)。
接下来的 n 行包含表格单元格的描述。具体来说,第 i 行包含 m 个空格分隔的整数 ai1,ai2,...,aim。如果 aij 等于 0,则单元格 (i, j) 不好。否则 aij 等于 1。保证至少有一颗电池是好的。保证没有一个好小区是死角。
输出
打印一个数字——西蒙实现他的想法所需的最少操作数。
示例
输入 #1
3 3 0 0 0 0 1 0 0 0 0
输出 #1
4
输入 #2
4 3 0 0 0 0 0 1 1 0 0 0 0 0
输出 #2
2
注意
在第一个示例中,操作顺序可以如下所示:
- 第一次需要选择单元格 (2, 2) 和角点 (1, 1)。
- 第二次您需要选择单元格 (2, 2) 和角点 (3, 3)。
- 第三次您需要选择单元格 (2, 2) 和角点 (3, 1)。
- 第四次您需要选择单元格 (2, 2) 和角点 (1, 3)。
在第二个示例中,操作顺序可以如下所示:
- 第一次需要选择单元格 (3, 1) 和角点 (4, 3)。
- 第二次需要选择单元格 (2, 3) 和角点 (1, 1)。