# 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 |