Кубик Риддика
Как известно, самой продаваемой игрушкой в истории является Кубик Рубика. Всего за всю историю было продано более 350 миллионов штук.
Один казахский бизнесмен решил повторить этот успех, создав упрощенную версию этой головоломки. Кубик Риддика представляет из себя прямоугольник размером n × m, состоящий из ячеек 1 × 1, каждая из которых раскрашена в какой-то цвет. За один ход разрешается циклически сдвигать любую строку или любой столбец в любую сторону на одну ячейку. Вот например, как сдвигается 2-я строка вправо и 3-й столбец вверх:
Решением головоломки является такая конфигурация, в которой в каждой строке либо в каждом столбце все ячейки одного цвета (выигрышная конфигурация).
Для начала продаж головоломки необходимо сделать оценку ее сложности, чем Вы и должны заняться. Для вычисления сложности будем использовать упрощенные правила: Вы должны сдвинуть сначала какие-то столбцы (возможно никакие), а затем какие-то строки (возможно никакие).
Вам будет дано описание конфигурации Кубика Риддика. Если из заданной конфигурации возможно по упрощенным правилам получить выигрышную, то сложность текущей конфигурации считается равной минимальному количеству ходов, необходимых для достижения выигрышной. Если же получить выигрышную конфигурацию по этим правилам невозможно, считается, что сложность равна 100500 (головоломка может быть все еще решаема по обычным правилам, но она слишком сложная).
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 5). Следующие n строк содержат по m целых чисел каждая описание головоломки. Каждое число это номер цвета, в который раскрашена соответствующая ячейка. Номера цветов целые числа от 1 до 100. Не гарантируется, что приведенное описание соответствует головоломке, решаемой даже обычными правилами.
Выходные данные
Выведите одно целое число - сложность заданной конфигурации головоломки.