logo AlgoBeat OnlineJudge
登录 注册

#104808. [BZOJ 4808] 马

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: 匿名

题目描述

众所周知,马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来,如果在要去的方向有别的棋子挡住(俗称"蹩马腿"),则不允许走过去。为了简化问题,我们不考虑这一点。马跟马显然不能在一起打起来,于是 rly 在一天再次借来了许多许多的马在棋盘上摆了起来……

但这次,他实在没兴趣算方案数了,所以他只想知道在 的矩形方格中摆马使其互不吃到的情况下的最多个数。但是,有一个很不幸的消息,rly 由于玩得太 Happy,质量本来就不好的棋盘被 rly 弄坏了,不过幸好只是破了其中的一些格子(即不能再放子了),问题还是可以继续解决的。

输入格式

一行,两个正整数

接下来 行,每行 个数,要么为 ,表示没坏,要么为 ,表示坏了。

输出格式

一行,输出最多的个数。

样例输入

2 3
0 1 0
0 1 0

样例输出

2

数据范围与提示

对于 的数据,

By FancyCoder