Областная олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Задача F. Футболки

Тима любит футболки. В городе есть очень крутой магазин футболок, который продает футболки $n$ цветов пронумерованных от $1$ до $n$, включительно. В течении $k$ дней магазин проводит масштабную акцию, где они будут продавать футболки некоторых цветов за полцены. Магазин опубликовал у себя на сайте таблицу $a$, где $a_{i,j}$ обозначает действует ли акция в j-й день на футболку цвета $i$ ($1$ если действует, иначе $0$). У Тимы есть порядок предпочтений цветов $p$, который является перестановкой чисел от $1$ до $n$. Любимый цвет Тимы это цвет $p_1$, второй самый любимый это цвет $p_2$ и т.д. Каждый день в течении $k$ дней он будет приходить в магазин, и среди тех цветов на которые действует акция в тот день, он купит одну футболку с наиболее любимым цветом. Формально, в i-й день он выберет самый минимальный $j$, что $a_{i, p_j}$ = $1$ и купит одну футболку с цветом $p_j$. Если в тот день нет ни одного цвета, на который действует акция, то он ничего не покупает. Тима хранит $p$ в тайне. Какое максимальное количество различных цветов может оказаться среди футболок, которое он купил за $k$ дней?

Формат входного файла

В первой строке задано два целых числа $n$ и $k$ ($1$ $\le$ $n$ $\le$ $10^5$, $1$ $\le$ $k$ $\le$ $14$). В следующих $n$ строках записано по $k$ символов — элементы $a$. Каждый символ является либо «0», либо «1».

Формат выходного файла

Выведите одно целое число — максимальное количество различных цветов, которое может оказаться среди футболок.

Примеры

Входные данные

4 3
111
110
001
110

Выходные данные

2

Входные данные

3 3
000
000
000

Выходные данные

0