A. Сдвиги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вам дана таблица размером n строк на m столбцов. В каждой ячейке таблицы записано число 0 или 1. За один ход можно выбрать какую-то из строк таблицы и циклически сдвинуть значения в ней на одну ячейку либо влево, либо вправо.

Циклически сдвинуть строку таблицы на одну ячейку вправо означает переместить значение каждой ячейки этой строки, кроме последней, в соседнюю ячейку справа, а значение последней ячейки переместить в первую ячейку. Аналогичным образом, но в обратную сторону выполняется циклический сдвиг строки таблицы влево. Например, если циклически сдвинуть строку «00110» на одну ячейку вправо — получится строка «00011», если же сдвинуть строку «00110» на одну ячейку влево — получится строка «01100».

Определите, за какое наименьшее количество ходов можно добиться того, что в каком-то из столбцов таблицы будут только единицы.

Входные данные

Первая строка содержит два целых числа, разделенные пробелом: n (1 ≤ n ≤ 100) — количество строк в таблице и m (1 ≤ m ≤ 104) — количество столбцов в таблице. Далее следуют n строк, каждая из которых содержит по m символов «0» или «1»: j-тый символ i-той строки описывает содержимое ячейки в i-той строке и j-ом столбце таблицы.

Гарантируется, что в описании таблицы не встречается никаких символов кроме «0» и «1».

Выходные данные

Выведите единственное число: наименьшее количество ходов, за которое можно в каком-то из столбцов таблицы получить только единицы. Если этого сделать нельзя, выведите -1.

Примеры
Входные данные
3 6
101010
000100
100000
Выходные данные
3
Входные данные
2 3
111
000
Выходные данные
-1
Примечание

В первом примере один из способов достижения цели с наименьшим количеством шагов таков: циклически сдвинем вторую строку один раз вправо, а третью — два раза влево. Тогда предпоследний столбец таблицы будет содержать только единицы.

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