Migrated from Lutece 3151 碎片整理

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

鸡煲终于来到了第三层 Boss 处，现在鸡煲的牌组中有 1 张「散热片（瓶装）」、$10^{100}$ 张「碎片整理」，遗物中有「干瘪之手」。拿到如此爽种的鸡煲面对觉醒者的战前宣言是……

"会赢的.jpg"

鸡煲的中央处理器可以看作为一个 $n$ 行 $m$ 列的 $01$ 矩阵，数字 $1$ 表示这个位置可以获得「集中」，数字 $0$ 表示这个位置没有「集中」。现在，每当鸡煲打出 $1$ 张「碎片整理」后，他可以进行如下操作：

• 在矩阵中选择一串全为 $1$ 的连续序列，方向可以是横向或纵向。
• 获得这串子序列上的「集中」，并将这串序列上的数字变为 $0$。

由于每打出一张「碎片整理」觉醒者会获得 $2$ 点力量，鸡煲想要在获得所有集中的前提下打出尽可能少的「碎片整理」。由于鸡煲忙着启动，现在请你帮助他解决这个问题。

Input

第一行两个正整数 $n,m(1\leq n,m\leq200)$。

接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 串。第 $i+1$ 行第 $j$ 列数字表示这个位置是否有「集中」，如果为 $1$，说明此处有「集中」，如果为 $0$，说明此处没有「集中」。

Output

输出一个整数，表示最少需要打出多少次「碎片整理」。

Samples

3 4
1011
1111
1100

4

Note

样例中至少需进行四次操作，其中一种方案如下：

第 $1$ 次操作后：

第 $2$ 次操作后：

第 $3$ 次操作后：

第 $4$ 次操作后：

Resources

2024 UESTC ICPC Training for Graph