Инна очень любит сладкое и игру «Матрица конфет». Сегодня она придумала новую игру — «Матрица конфет 2: перезагрузка».
Поле для новой игры представляет собой прямоугольную таблицу размера n × m. В каждой строке этой таблицы одна клетка занята фигуркой гномика, одна клетка занята конфеткой, остальные клетки строки свободны. Игра длится несколько ходов. На каждом ходе игрок должен выбрать все строки матрицы, в которых гномики не стоят в конфетах, и крикнуть: «Побежали!». После чего все гномики в выбранных строках начинают синхронно передвигаться вправо. За одну секунду каждый гномик шагает в соседнюю клетку, которая находится правее его текущей клетки. Передвижения продолжаются до тех пор пока не случится одно из событий:
- какой-то гномик в одной из выбранных строк находится в самой правой клетке своей строки;
- какой-то гномик в выбранных строках находится в клетке с конфетой.
Цель игры — сделать так, чтобы все гномики находились в клетках с конфетами.
Инна — большой молодец, ведь она придумала такую интересную игру. А как же вы? Ваша задача — сыграть в эту игру оптимальным образом. А именно, по заданному игровому полю сказать, какое минимальное количество ходов потребуется игроку, чтобы добиться цели игры.
Выходные данные
В единственной строке выведите целое число — минимальное количество ходов, необходимое для достижения цели игры, либо -1, если достичь ее на данном игровом поле невозможно.