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

Есеп C. Футболкалар

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

1 second

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

256 megabytes

Тима футболкаларды жақсы көреді. Қалада $1$-ден $n$-ға дейін нөмірленген $n$ түсті футболкалар сататын өте керемет футболкалар дүкені бар. $k$ күн ішінде дүкен ауқымды акция өткізеді, онда олар кейбір түстердің футболкаларын жарты бағамен сатады. Дүкен өзінің веб-сайтында $a$ кестесін жариялады. Мұнда $a_{i,j}$ акция $j$-ші күні $i$-ші түсті футболкаға жарамдылығын көрсетеді (егер жарамды болса 1, әйтпесе 0). Тимада $1$-ден $n$-ға дейінгі сандарды алмаластыруы болып табылатын $p$ түстерін таңдау тәртібі бар. Тиманың сүйікті түсі - $p_1$ түсі, екінші сүйіктісі - $p_2$ түсі және т.б. Күн сайын $k$ күн ішінде ол дүкенге келіп, және сол күні акция жарамды түстердің ішінде ол ең сүйікті түсі бар бір футболка сатып алады. Басқаша айтқанда, $i$ күні ол $a_{i,{p_j}} = 1$ болатын ең төменгі $j$ таңдайды және $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 )