#joi2008yoe. [joi2008yo_e]おせんべい
[joi2008yo_e]おせんべい
问题
IOI制果采用自创传统制法炼制煎饼。这种传统制法是在木炭火上将正面煎熟一定时间后,翻转到背面再继续用木炭火烤熟。在遵守这一传统的同时,他们使用机器来制作煎饼。这台机器将煎饼以纵向 () 行、横向 () 列的长方形排列进行烘烤。通常情况下,机器是自动运行的,当正面烤熟后,立即将煎饼翻转并烤熟背面。
有一天,在烘烤煎饼的过程中,正准备翻转煎饼时发生了地震,导致一些煎饼提前翻面。幸运的是,木炭状况依然适宜,但如果再用正面烤烤,将超过规定的烤制时间,导致煎饼的正面过度烤制,无法作为商品发货。因此,他们迅速将机器切换到手动操作模式,只翻转尚未翻面的煎饼。这台机器可以同时翻转几行横向煎饼或者几列纵向煎饼,但遗憾的是,不能每次只翻转一块煎饼。
考虑到翻转需要时间,如果没有及时翻面,未翻面的煎饼的正面会过度烤制,无法作为商品发货。因此,可以选择同时翻转几行横向煎饼,然后继续同时翻转几列纵向煎饼,以便既不过度烤正面,又能烤熟双面,也就是尽量多地制作出能够发货的煎饼。我们将考虑不翻转任何横向行或者不翻转任何纵向列的情况。请编写一个程序来输出可以发货的煎饼的最大数量。
地震后,煎饼处于如下图所示的状态。黑色的圆表示正面已烤好,白色的圆表示背面已烤好。
翻转第一行后,状况如下图所示。
进一步地,翻转第一列和第五列后,状况如下图所示。此时,可以发货的煎饼共有9片。
提示
注意到 的上限10比 的上限 要小。
输入
第一行包含两个整数 和 (),以空格分隔。接下来的 行表示地震后煎饼的状态。第 () 行 () 包含 个整数 ,以空格分隔,其中 表示第 行第 列的煎饼状态。 是1表示正面已烤好,是0表示背面已烤好。
输出
输出是一个表示可以发货的煎饼最大数量的单行。
示例 1
2 5
0 1 0 1 0
1 0 0 0 1
输出示例 1
9
示例 2
3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1
输出示例 2
15