You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T4 矩阵（matrix）

题目描述

小 C 有一个大小为 $n\times m$ 的 01 矩阵 $A$。

小 C 认为第 $i$ 列是好的当且仅当第 $i$ 列中 1 刚好出现了一次，即 $\sum_{j=1}^n [A_{j,i}=1]=1$。

小 C 可以进行以下操作任意次：选择矩阵 $A$ 中的某一行将其 01 翻转（即 0 变成 1，1 变成 0）。

小 C 想要让矩阵 $A$ 中好的列数尽可能多，你能告诉他这个最大值吗？

输入格式

第一行输入两个数字 $n,m$，分别表示矩阵的长与宽。

接下来 $n$ 行，每行包含一个长度为 $m$ 仅由 01 组成的字符串。

输出格式

共一行，输出一个整数，表示矩阵 $A$ 中最多的好的列数。

样例 1 输入

3 4
0101
0110
1011

样例 1 输出

3

样例 1 解释

将每一行都进行翻转，矩阵 $A$ 变为：

1010
1001
0100

此时第 $2,3,4$ 列是好的，故答案为 $3$。

样例 2 输入

3 3
101
111
000

样例 2 输出

2

其余样例见下发文件。

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n,m \le 16$。
• 对于 $40\%$ 的数据，保证 $n,m \le 100$。
• 对于 $60\%$ 的数据，保证 $n,m\le 500$。
• 对于另 $20\%$ 的数据，保证 $n\times m \le 70000$。
• 对于 $100\%$ 的数据，保证 $1\le n,m\le 3\times 10^5$，$1\le n\times m\le 3\times 10^5$。