Problem G
On-Call Team
An IT company has formed an on-call team of software engineers who will manage their backend services and make sure that these services run without interruption. When services go down, for each service that is down the on-call team must dispatch one member who is familiar with that service to take care of its issue. One team member can handle at most one service at a time. The company wants to evaluate the robustness level of the on-call team, which is defined as the maximum value $k$ such that any $k$ services that go down simultaneously can be handled by the on-call team.
Input
The first line of input contains two integers $n$ ($1 \leq n \leq 3 \cdot 10^4$) and $m$ ($1\leq m \leq 20$), where $n$ is the number of engineers and $m$ is the number of backend services.
Each of the next $n$ lines contains a string of binary digits of length $m$, describing the $n$ software engineers’ familiarity with the $m$ services. The $j^{\text {th}}$ digit on the $i^{\text {th}}$ line is $1$ if software engineer $i$ is familiar with service $j$, and $0$ otherwise.
It is guaranteed that for each of the $m$ services there exists at least one software engineer who is familiar with it.
Output
Output a single integer, which is the robustness level of the on-call team.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 6 001101 111001 001110 100100 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 001 001 110 |
1 |
