Вишивка хрестиком
Археологи виявили тканину, прикрашену вишивкою хрестиком, виконаною кількома нитками. Було встановлено такі правила:
Тканина має сітку з квадратними осередками.
Кожен стібок покриває діагональ одного осередку сітки. Стібки можуть бути на обох сторонах тканини, але кожен з них може бути лише на одній стороні (нитка може починатися, закінчуватися і проходити через тканину тільки у вершинах сітки).
На кожній діагоналі кожного осередку з кожної сторони тканини може бути не більше одного стібка.
Кожна нитка виконує кілька стібків, розташованих почергово на різних сторонах тканини. (Це означає, що два послідовних стібка однієї нитки лежать на різних сторонах тканини і з'єднуються у вершині сітки).
Голка може проходити крізь тканину тільки у вершинах сітки.
На рисунку показано фрагмент вишивки з шести стібків. Розмір сітки 4×5. Лицьова сторона тканини зображена на верхньому рисунку. Стібки на лицьовій стороні тканини показані суцільними лініями. Стібки на зворотному боці тканини відображені лініями з точками. На нижньому рисунку тканина орієнтована так само, як і на верхньому. Усі стібки зворотної сторони тканини тут показані суцільними лініями. Лицьові стібки, які не збігаються з зворотними, відображаються прямими з точками. Можна помітити, що стібки можуть покривати обидві діагоналі одного осередку. Наведену вишивку хрестиком можна виконати, використовуючи не менше чотирьох ниток.
Археологи прагнуть з'ясувати, чи дійсно заданий візерунок виконаний з використанням мінімальної кількості ниток. Напишіть програму, яка визначить найменшу кількість ниток, необхідну для створення заданого візерунка.
Вхідні дані
Перша рядок містить два числа N і M. Це розмір сітки по вертикалі (N) і по горизонталі (M), тобто кількість осередків відповідно у вертикальному і горизонтальному рядку (1 ≤ N, M ≤ 200). Кожен з наступних 2N рядків містить M символів. Кожен символ описує одну клітинку сітки. Перші N рядків відповідають лицьовій стороні тканини, а останні N рядків - зворотній стороні тканини. Використовуються символи ".", "/", "\" і "X" (крапка означає порожню клітинку).
Для отримання більшої інформації зверніться до рисунка. Він відповідає наведеному прикладу.
Вихідні дані
Виведіть одне число - найменшу кількість ниток, якими можна вишити заданий візерунок.