3217 - 炸弹小人

一个N行M列的网格,在W位置为墙,E位置为敌人。如果将炸弹小人放在位置(i,j)处,则第i行和j列的敌人都会炸死,但如果有墙,则炸弹不能穿透墙。在有敌人的位置和墙的位置都不能放炸弹。例如:

0E0E

E0WE

0E00

放炸弹的最优位置有多个,(1,1)、(2,2)或(3,4),均可以炸死3个敌人。

输入

第一行输入证书N和M。 后面的N行M列为网格。用0表示可以防止炸弹的位置,用1表示敌人,用2表示墙

输出

一个整数,最多能炸死多少人敌人。

样例

输入

3 4
0 1 0 1
1 0 2 1
0 1 0 0

输出

3

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题