Problem Name: Rice crackers
Problem
Problem Description: IOI Seika has been making rice crackers using traditional methods since its inception. This traditional method is to bake one side on charcoal for a certain time, then flip it over and bake the other side for a certain time on charcoal. While maintaining this tradition, they bake rice crackers with a machine. This machine arranges the rice crackers in a rectangular shape with R (1 ≤ R ≤ 10) rows and C (1 ≤ C ≤ 10000) columns vertically. Normally, it operates automatically and flips all the rice crackers over when the top side is cooked.
One day, during the baking process, an earthquake occurred just before flipping the rice crackers, and some of the rice crackers were flipped over. Fortunately, the charcoal was still in good condition, but if they continued cooking the top side, they would exceed the cooking time specified by the tradition since the beginning of the company, and the top side of the rice crackers would be overcooked and unable to be shipped as a product. Therefore, they quickly switched the machine to manual operation and tried to flip only the rice crackers that hadn't been flipped yet. This machine can flip several rows horizontally at the same time or several columns vertically at the same time, but unfortunately, it cannot flip one rice cracker at a time.
If it takes too long to flip, the top side of the rice crackers that were not flipped due to the earthquake will be overcooked, and they will not be able to be shipped as products. Therefore, they decided to flip several rows horizontally at once and then several columns vertically at once to cook both sides of the rice crackers without overcooking the top side, that is, to maximize the number of rice crackers that can be shipped as products. The problem is to write a program that outputs the maximum number of rice crackers that can be shipped. It is also assumed that no row or column will be flipped.
Assume that after the earthquake, the rice crackers are in the state shown in the following figure. Black circles represent the state where the top side is cooked, and white circles represent the state where the back side is cooked.
When the first row is flipped, the state becomes as follows.
Further, when the first and fifth columns are flipped, the state becomes as follows. In this state, it is possible to ship 9 rice crackers.
Hint
Note that the upper limit of R, 10, is smaller than the upper limit of C, 10000.
Input
The input consists of multiple datasets. Each dataset is given in the following format.
The first line of the input contains two integers R and C (1 ≤ R ≤ 10, 1 ≤ C ≤ 10000) separated by a space. The following R lines represent the state of the rice crackers immediately after the earthquake. The i-th line (1 ≤ i ≤ R) consists of C integers a
i,1
, a
i,2
, ..., a
i,C
separated by a space, where a
i,j
represents the state of the rice cracker in the i-th row and j-th column. If a
i,j
is 1, it means that the top side is cooked, and if a
i,j
is 0, it means that the back side is cooked.
When C = R = 0, the input is terminated. The number of datasets is no more than 5.
Output
For each dataset, output the maximum number of rice crackers that can be shipped as products on one line.
Sample Input and Output
Sample Input
2 5
0 1 0 1 0
1 0 0 0 1
3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1  
0 0
Sample Output
9
15
The problem statement and test data used in the automatic judgment are problem statements and scoring test data created and published by the
Japan Information Olympiad Committee
.