Пусть задана матрица b размера x × y, определим операцию разворота матрицы b. Разворотом матрицы b называется матрица c размера 2x × y, обладающая свойствами:
У Сережи есть матрица a размера n × m. Он хочет найти такую матрицу b, что из нее можно получить матрицу a, выполнив несколько (возможно, ноль) разворотов. Какое минимальное количество строк может содержать такая матрица?
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 100). Следующие n строк содержат по m целых чисел — элементы матрицы a. В i-й строке записаны целые числа ai1, ai2, ..., aim (0 ≤ aij ≤ 1) — i-я строка матрицы a.
В единственную строку выведите ответ на задачу — минимальное количество строк матрицы b.
Во первом тестовом примере ответом является матрица b размера 2 × 3:
001110
Если применить к этой матрице операцию разворота, получится заданная во входных данных матрица a:
001110110001
4 3 0 0 1 1 1 0 1 1 0 0 0 1
2
3 3 0 0 0 0 0 0 0 0 0
3
8 1 0 1 1 0 0 1 1 0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач