棋盘覆盖
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有一个 N×M 的棋盘，棋盘上的每个小格子都是边长为 1 的正方形。其中有些格子是好格子，有些是坏格子。
现在你要用长条形的骨牌来覆盖所有的坏格子。
每一个骨牌的宽度均为 1，长度由你来决定。骨牌必须水平或竖直铺在坏格子的上方。骨牌可以重叠铺放，但是不能铺到好格子上。
问：要把所有的坏格子全部覆盖，至少需要多少个骨牌？
输入格式
第一行：两个整数 。
接下来一个 N×M 的字符矩阵用来描述棋盘，其中 1 表示坏格子，0 表示好格子。
输出格式
一个整数，表示答案。
样例输入
3 4
0010
0111
1010
样例输出
3
数据范围
