P12245 Common Interests

Shared interests form a solid foundation for lasting friendships.

There are $n$ students in Little O's grade, numbered $1 \sim n$. The school surveyed $m$ activities. Each student is interested in some activities and not in others. Let $a_{i,j}$ indicate whether student $i$ is interested in activity $j$, where $a_{i,j} = 1$ means interested and $a_{i,j} = 0$ means not interested. For any two students $i$ and $j$, their **number of common interests** is the count of activities $k$ where $a_{i,k} = a_{j,k} = 1$, i.e., the number of activities both students are interested in. Each student $x$ will find all students $y$ who have the maximum **number of common interests** with $x$ and send them friendship invitations. If multiple students $y$ satisfy this condition, $x$ will send invitations to all of them. Little O (student $1$) wants to receive as many invitations as possible. He can choose one activity $i$ where he is not initially interested (i.e., $a_{1,i} = 0$) and change it to $a_{1,i} = 1$. He may also choose not to modify any activity. Note: At most one modification is allowed. What is the maximum number of students who will send invitations to Little O after making at most one modification?

The input consists of $n+1$ lines: - Line $1$: Two integers $n$ and $m$, representing the number of students and activities. - Lines $2$ to $n+1$: Each line contains $m$ integers. The $j$-th integer in line $i+1$ represents $a_{i,j}$.

Output one integer: the maximum number of students who will invite Little O.

### Sample #1 Explanation Initially, students $2$ and $3$ each have $1$ common interest with each other (activity $3$). Their common interests with Little O are $0$. Modifications: - No modification: $0$ invitations. - Modify $a_{1,1}$ to $1$: Student $2$ invites Little O ($1$ invitation). - Modify $a_{1,2}$ to $1$: Student $3$ invites Little O ($1$ invitation). - Modify $a_{1,3}$ to $1$: Both students $2$ and $3$ invite Little O ($2$ invitations). Thus, the maximum is $2$. ### Sample #2 Explanation Adding student $4$ (who has $2$ common interests with students $2$ and $3$). Little O's maximum common interests with any student after modification cannot exceed $1$, so the answer is $0$. For $100\%$ data: - $2 \le n \le 500$ - $1 \le m \le 500$ - $a_{i,j} \in \{0,1\}$ | Test Case | $n$ Range | $m$ Range | Special Properties | | :-------: | :-------: | :-------: | :-----------------: | | $1$ | $n=2$ | $m \le 50$ | None | | $2\sim 4$ | $n \le 50$ | $m \le 50$ | None | | $5\sim 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$ | None | Special Properties: - A: For all $1 \le i \le m$, $a_{1,i} = 0$. - B: For all $1 \le i \le n$, $a_{i,1} = 0$.