Инна очень любит сладкое и игру «Матрица конфет». Сегодня она придумала новую игру — «Матрица конфет 2: перезагрузка».

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

• какой-то гномик в одной из выбранных строк находится в самой правой клетке своей строки;
• какой-то гномик в выбранных строках находится в клетке с конфетой.

Цель игры — сделать так, чтобы все гномики находились в клетках с конфетами.

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