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