Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Sharfik
В партизанском отряде сегодня генеральский смотр!
На смотры отряд всегда выстраивается в один и тот же прямоугольник A на B солдат. Но вот незадача: на смотр приезжает генерал, который хочет видеть целый ряд из солдат в ушанках (примета хорошая!), а не у всех они есть.
И каждый солдат ещё хочет стоять между теми же боевыми товарищами, что и до этого. Да и шапками обмениваться, что-то не хочется (мало ли в каких канавах Сидоров ползал!).
Поэтому Сергей, работавший писарем, предложил воспользоваться циклическими сдвигами солдат по колоннам: так порядок точно сохранится, да и солдатам не надо будет ничего сложного придумывать. А чтобы было ещё проще, надо бы узнать заранее сколько всего сдвигов понадобится...
Входные данные. В первой строке указываются размеры полка A и B (натуральные числа, не больше 100), через пробел. Далее в A строках указано наличие шапки у B бойцов: 0, если ушанки нет, 1, если есть. Партизаны стоят плотненько, поэтому никаких пробелов между соседними бойцами в данных быть не может!
Выходные данные. Целое число – минимальное количество перестроений (циклических сдвигов на 1). В случае, если так перестроиться невозможно, вывести -1.
Пример:
|
Ввод
|
4 3
100
110
000
001
|
|
Вывод
|
2
|
Здесь необходимо циклически сдвинуть самый правый ряд или на два партизана вперёд, или на два назад.
Для отправки решений необходимо выполнить вход.
|