Maximizing Invitations

In a class there are $$n$$ students with student IDs from $$1$$ to $$n$$. The school conducted a survey on $$m$$ activities. Each student is interested in some of the activities and not in others. We denote by $$a_{i,j}$$ the answer of student $$i$$ on activity $$j$$: $$a_{i,j} = 1$$ means the student is interested in the activity, and $$a_{i,j} = 0$$ otherwise.

For any two distinct students $$i$$ and $$j$$, their common interest count is defined as $$ common(i,j)=\sum_{k=1}^{m} \mathbf{1}\{a_{i,k}=1 \text{ and } a_{j,k}=1\}, $$ which is the number of activities both are interested in.

For each student $$x$$ (with $$x \ge 2$$), he/she finds the student(s) $$y$$ (with $$y\neq x$$) that maximize the common interest count. That is, student $$x$$ sends a friend invitation to every student $$y$$ satisfying $$ common(x,y)=\max_{z\neq x} common(x,z). $$

Student $$1$$ (Little O) wants to receive as many invitations as possible. He is allowed to modify at most one activity in his own interest list: he may choose an activity $$i$$ for which $$a_{1,i}=0$$ and change it to $$1$$. He may also choose to make no modification. Note that he can modify at most one activity.

Your task is to compute the maximum number of invitations Little O can receive after at most one modification.

Details:

• Let the original common interest between student $$x$$ and student $$1$$ be $$f(x,1)=\sum_{k=1}^{m}\mathbf{1}\{a_{x,k}=1 \text{ and } a_{1,k}=1\}.$$
• If Little O modifies activity $$i$$ (i.e. changes $$a_{1,i}$$ from 0 to 1), then for any student $$x$$ his new common interest becomes $$f(x,1)+\delta,$$ where $$\delta=1$$ if $$a_{x,i}=1$$, and $$0$$ otherwise.
• For any student $$x\ge2$$, let $$T_x = \max_{y\ge 2, y\neq x} common(x,y).$$ Student $$x$$ will send an invitation to Little O if the updated value satisfies $$f(x,1)+\delta \ge T_x.$$

Determine the maximum number of students (with IDs $$2$$ to $$n$$) who can send an invitation to Little O.

inputFormat

The first line contains two integers $$n$$ and $$m$$, representing the number of students and the number of activities, respectively.

Then follow $$n$$ lines, each containing $$m$$ integers (either 0 or 1). The first line represents Little O (student 1) and the subsequent lines represent students 2 to $$n$$.

outputFormat

Output a single integer representing the maximum number of invitations Little O can receive after at most one modification.

sample

2 1
0
1

1