Главный завод города N выпускает велосипеды и их комплектующие. Для хранения деталей велосипеда используются заготовленные отлитые жесткие формы из алюминия. Эти формы расположены внизу на платформе, а конвеер, перевозящий детали велосипедов, останавливается над ними и опускает детали в формы. Руководству завода стал интерестен вопрос оптимального расположения детали в отлитой форме, и они обратились к вам за помощью, как к лучшему программисту компании.
Вам дали упрощенные модели детали и формы — две прямоугольные таблицы detail и mold/ Сама деталь представлена в detail фигурой, образованной всеми символами '*' в таблице. Аналогично, форма представлена в mold фигурой, образованной всеми символами '#'. Руководство компании гарантировано вам, что все фигуры у них связные, то есть что от любой клетки детали и формы можно добраться до любой другой соответственно, переходя каждый раз в соседнюю по стороне клетку. Будем называть «зацепом» символы '#' и '*', идущие в одной строке подряд именно в таком порядке. Например, в состоянии, указанном ниже, ровно 4 зацепа.
....*****..
...#*#*..
...#*#**.
#########
Теперь вас просят решить следующую задачу: надо понять, как нужно расположить деталь над формой, чтобы после опускания ее в форму количество зацепов было максимально. Опускание в форму производится следующим образом: деталь располагается где угодно над формой, а затем опускается вниз до упора.
5 6
******
*.*.*.
*.*.*.
*.....
*.....
3 8
#.#.#.#.
#.#.#.#.
#######.
4