P12245 共同兴趣

共同的兴趣爱好是一段友谊坚实的基础。

小 O 所在年级有 $n$ 名学生，学号为 $1 \sim n$，学校对 $m$ 项活动进行了调查。每位学生对部分活动感兴趣，对于其他活动则不感兴趣。我们用 $a_{i,j}$ 来表示学号为 $i$ 的学生是否对第 $j$ 项活动感兴趣，其中 $a_{i,j} = 1$ 表示感兴趣，$a_{i,j} = 0$ 表示不感兴趣。 对于任意两位学生 $i$ 和 $j$，他们的共同兴趣数是指那些满足 $a_{i,k} = a_{j,k} = 1$ 的活动 $k$ 的数量，即两位学生都感兴趣的活动数。 每个学生 $x$ 会寻找与自己共同兴趣数最多的学生 $y$，并向其发出交友的邀约。如果有多个学生 $y$ 满足条件，$x$ 会向所有这些学生发出邀约。 小 O 的学号为 $1$，他希望能够收到更多同学的邀约。为此，他可以选择一项自己不感兴趣的活动 $i$，将其从 $a_{1,i} = 0$ 修改为 $a_{1,i} = 1$。当然，他也可以选择不修改任何活动。注意，最多只能修改一项活动。 请问，在进行最多一次修改后，最多有多少同学会向小 O 发出邀约？

无

无

#### 样例 #1 解释 初始时学号为 $2$，$3$ 的两位学生的共同兴趣数为 $1$，因为他们同时对第 $3$ 项活动感兴趣。他们和小 O 的共同兴趣都是 $0$。接下来小 O 进行修改： - 如果不修改，则 $2$ 号和 $3$ 号会互相发出邀约，给小 O 发出邀约的人数为 $0$。 - 如果将 $a_{1,1}$ 修改为 $1$，则小 O 和 $2$ 号的共同兴趣数变为 $1$，$2$ 号会对小 O 发出邀约，给小 O 发出邀约的人数为 $1$。 - 如果将 $a_{1,2}$ 修改为 $1$，则小 O 和 $3$ 号的共同兴趣数变为 $1$，$3$ 号会对小 O 发出邀约，给小 O 发出邀约的人数为 $1$。 - 如果将 $a_{1,3}$ 修改为 $1$，则小 O 和其他两位学生的共同兴趣数均变为 $1$，$2$ 位学生均会对小 O 发出邀约。 所以最多有 $2$ 位学生会对小 O 发出邀约。 #### 样例 #2 解释 与样例 #1 相比，多出了学号为 $4$ 的学生，他和 $2$ 号和 $3$ 号学生的共同兴趣数为 $2$，无论怎么修改，小 O 和任何同学的共同兴趣数不会超过 $1$，故答案为 $0$。 ### 数据范围 对于 $100\%$ 的数据，$2\le n\le 500$，$1\le m\le 500$，$0\le a_{i,j}\le 1$。 具体测试点限制如下： | 测试点编号 | $n$ 的范围 | $m$ 的范围 | 特殊性质 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $n=2$ | $m\le 50$ | 无 | | $2\sim 4$ | $n\le 50$ | $m\le 50$ | 无 | | $5,6$ | $n\le 500$ | $m=1$ | A | | $7\sim 10$ | $n\le 500$ | $m\le 500$ | A | | $11\sim 14$ | $n\le 500$ | $m\le 500$ | B | | $15\sim 20$ | $n\le 500$ | $m\le 500$ | 无 | 特殊性质 A：对于 $1\le i\le m$，$a_{1,i}=0$。 特殊性质 B：对于 $1\le i\le n$，$a_{i,1}=0$。