对于一个大小为 $n \times m$ 的 01 矩阵 $M$（其元素均为 0 或 1，下同），如果其索引集合 $S$ 满足以下两个条件，则称其为“好”索引集：

1. 对于所有 $(u, v) \in S$，都有 $M_{u,v} = 0$。
2. 对于每个满足 $M_{i,j} = 0$ 的元素（$1 \le i \le n, 1 \le j \le m$），都存在一个索引 $(u, v) \in S$ 同时满足以下两个条件：
   • $i = u$ 或 $j = v$
   • 对于所有满足 $(x - i)(x - u) \le 0$ 且 $(y - j)(y - v) \le 0$ 的 $x, y$，都有 $M_{x,y} = 0$

此外，01 矩阵的值定义为其所有“好”索引集中最小的大小。

现在给定一个 012 矩阵，你需要将其中所有的 2 替换为 0 或 1，并确定在所有替换方案中，矩阵值的最小值。显而易见，总共有 $2^{cnt_2}$ 种替换方案，其中 $cnt_2$ 表示给定矩阵中 2 的个数。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n, m \le 8$)，表示给定 012 矩阵的大小。 接下来 $n$ 行，每行包含一个长度为 $m$ 的 012 字符串，其中第 $i$ 行的第 $j$ 个字符表示矩阵元素 $M_{i,j}$。

输出格式

输出一行，包含一个整数，表示替换后矩阵值的最小值。

样例

输入 1

3 7
0001101
0201020
0001101

输出 1

3

说明

一种可能的替换方案为：

0001101
0101000
0001101

其中一个最小的“好”索引集为 $\{(1, 1), (2, 6), (3, 3)\}$。