#joi2008yoe. [joi2008yo_e]おせんべい

[joi2008yo_e]おせんべい

问题

IOI制果采用自创传统制法炼制煎饼。这种传统制法是在木炭火上将正面煎熟一定时间后,翻转到背面再继续用木炭火烤熟。在遵守这一传统的同时,他们使用机器来制作煎饼。这台机器将煎饼以纵向 RR (1R101 \leqq R \leqq 10) 行、横向 CC (1C100001 \leqq C \leqq 10000) 列的长方形排列进行烘烤。通常情况下,机器是自动运行的,当正面烤熟后,立即将煎饼翻转并烤熟背面。

有一天,在烘烤煎饼的过程中,正准备翻转煎饼时发生了地震,导致一些煎饼提前翻面。幸运的是,木炭状况依然适宜,但如果再用正面烤烤,将超过规定的烤制时间,导致煎饼的正面过度烤制,无法作为商品发货。因此,他们迅速将机器切换到手动操作模式,只翻转尚未翻面的煎饼。这台机器可以同时翻转几行横向煎饼或者几列纵向煎饼,但遗憾的是,不能每次只翻转一块煎饼。

考虑到翻转需要时间,如果没有及时翻面,未翻面的煎饼的正面会过度烤制,无法作为商品发货。因此,可以选择同时翻转几行横向煎饼,然后继续同时翻转几列纵向煎饼,以便既不过度烤正面,又能烤熟双面,也就是尽量多地制作出能够发货的煎饼。我们将考虑不翻转任何横向行或者不翻转任何纵向列的情况。请编写一个程序来输出可以发货的煎饼的最大数量。

地震后,煎饼处于如下图所示的状态。黑色的圆表示正面已烤好,白色的圆表示背面已烤好。

2008-yo-t5-1.png

翻转第一行后,状况如下图所示。

2008-yo-t5-2.png

进一步地,翻转第一列和第五列后,状况如下图所示。此时,可以发货的煎饼共有9片。

2008-yo-t5-3.png

提示

注意到 RR 的上限10比 CC 的上限 1000010000 要小。


输入

第一行包含两个整数 RRCC (1R10,1C100001 \leqq R \leqq 10, 1 \leqq C \leqq 10000),以空格分隔。接下来的 RR 行表示地震后煎饼的状态。第 (i+1i + 1) 行 (1iR1 \leqq i \leqq R) 包含 CC 个整数 ai,1,ai,2,,ai,Ca_{i,1}, a_{i,2}, …, a_{i,C},以空格分隔,其中 ai,ja_{i,j} 表示第 ii 行第 jj 列的煎饼状态。ai,ja_{i,j} 是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