Вам дана таблица размером n строк на m столбцов. В каждой ячейке таблицы записано число 0 или 1. За один ход можно выбрать какую-то из строк таблицы и циклически сдвинуть значения в ней на одну ячейку либо влево, либо вправо.
Циклически сдвинуть строку таблицы на одну ячейку вправо означает переместить значение каждой ячейки этой строки, кроме последней, в соседнюю ячейку справа, а значение последней ячейки переместить в первую ячейку. Аналогичным образом, но в обратную сторону выполняется циклический сдвиг строки таблицы влево. Например, если циклически сдвинуть строку «00110» на одну ячейку вправо — получится строка «00011», если же сдвинуть строку «00110» на одну ячейку влево — получится строка «01100».
Определите, за какое наименьшее количество ходов можно добиться того, что в каком-то из столбцов таблицы будут только единицы.
Выходные данные
Выведите единственное число: наименьшее количество ходов, за которое можно в каком-то из столбцов таблицы получить только единицы. Если этого сделать нельзя, выведите -1.
Примечание
В первом примере один из способов достижения цели с наименьшим количеством шагов таков: циклически сдвинем вторую строку один раз вправо, а третью — два раза влево. Тогда предпоследний столбец таблицы будет содержать только единицы.
Во втором примере строки нельзя сдвинуть так, чтобы образовался столбец, содержащий только единицы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 6
101010
000100
100000
|
3
|
|
2
|
2 3
111
000
|
-1
|