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