3-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

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

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Тима любит футболки. В городе есть очень крутой магазин футболок, который продает футболки $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 <= n <= 10^5$, $1 <= k <= 14$). В следующих $n$ строках записано по $k$ символов — элементы $a$. Каждый символ является либо «0», либо «1».

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

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

Система оценки

Данная задача содержит $6$ подзадач, в которых выполняются следующие ограничения:

1. Тесты из условия. Оценивается в $0$ баллов.
2. $n$, $k <= 2$. Оценивается в $9$ баллов.
3. $n$, $k <= 8$. Оценивается в $18$ баллов.
4. $n$, $k <= 14$. Оценивается в $22$ баллов.
5. $n <= 10000$, $k <= 14$. Оценивается в $29$ баллов.
6. Исходные условия задачи. Оценивается в $22$ баллов.

Примеры:

Вход

4 3
111
110
001
110

Ответ

2

Вход

3 3
000
000
000

Ответ

0

( Temirlan Satylkhanov )