| Когнитивные технологии. Финал 2024 |
|---|
| Finished |
Мадока недавно нашла свой фотоальбом из детского сада. И она хочет вырезать как можно больше из него фотографий, так как они ей не нравятся. Но при этом в нем есть фотки со своим любимым попугайчиком и она их никак не хочет трогать.
Фотоальбом представляет собой прямоугольник $$$n \times m$$$, где в каждой клетке содержится ровно одна фотография. Также для каждой фотографии известно, есть ли на ней попуг. Мадока может вырезать только подпрямоугольники фотоальбома. Но при том вырезанные подпрямоугольники не могут пересекаться или касаться по сторонам.
Так, например, следующие прямоугольники нельзя вырезать, так как они касаются по стороне:
Поэтому Мадоке стало интересно, а какое максимальное количество фотографий она может вырезать, соблюдая правила, и чтобы ни одна фотка с попугом не была вырезана.
Данная задача состоит из нескольких наборов тестовых случаев.
В первой строке задано единственное число $$$t$$$ ($$$1 \leq t \leq 3000$$$) — количество тестовых случаев. Затем идет их описание.
В первой строке каждого тестового случая заданы два числа $$$n, m$$$ ($$$ 1 \leq n \leq 5, 1 \leq m \leq 10^4$$$).
Гарантируется, что сумма $$$m$$$ по всем тестовым случаям не превосходит $$$10^4$$$
Затем идут $$$n$$$ бинарных строк $$$a_1 a_2 \ldots a_m$$$, где равенство $$$a_j = 1$$$ означает, что в этой строке $$$j$$$-я фотография содержит попуга и ее нельзя вырезать.
Для каждого тестового случая выведите в единственной строке максимальное количество фотографий, которое можно вырезать, чтобы выполнялось условие.
32 30000104 31010000000114 3000100000001
4 6 7
Примеры оптимальных ответов на семплы
