19758번 - Головоломка 다국어

Дима играет в логическую компьютерную игру. Очередной уровень устроен следующим образом: у Димы есть клетчатая фигура, составленная из единичных квадратов. Ее необходимо правильным образом уронить на препятствие, также составленное из единичных квадратов. Фигура и препятствие являются связными: от любого квадрата фигуры можно добраться до любого другого, переходя между квадратами по стороне, аналогичное свойство выполнено для препятствия.

Исходно фигура находится сверху над препятствием так, что любой квадрат фигуры выше любого квадрата препятствия. Дима может произвольным образом переместить фигуру по горизонтали, а затем нажать на специальную кнопку, и фигура опустится вниз до упора. После этого за каждую пару соседних по горизонтали единичных квадратов, таких что левый квадрат принадлежит препятствию, а правый --- фигуре, Дима получает одно очко. Если Дима расположит фигуру так, что при падении вниз она не упрётся в препятствие, то Дима не получит очков.

Помогите Диме решить головоломку оптимальным образом.

Например, если у Димы есть фигура и препятствие, показанные на рисунке ниже, выгоднее всего уронить фигуру следующим образом:

В этом случае количество очков, набранных Димой, будет равно 4.

В первой строке ввода содержатся два числа $n_f$ и $m_f$ --- размеры фигуры ($1 \le n_f, m_f \le 300$). В каждой из следующих $n_f$ строк содержатся по $m_f$ символов --- описание фигуры, <<*>> означает квадрат, принадлежащий фигуре, <<.>> --- пустой квадрат.

В следующей строке содержатся два числа $n_o$ и $m_o$ --- размеры препятствия ($1 \le n_o, m_o \le 300$). В каждой из следующих $n_o$ строк содержатся по $m_o$ символов --- описание препятствия, <<\#>> означает квадрат, принадлежащий препятствию, <<.>> --- пустой квадрат.

Гарантируется, что фигура и препятствие представляют собой непустые связные множества единичных квадратов.

Выведите максимальное количество очков, которое Дима может получить.

В тестовом примере оптимальный способ уронить фигуру показан на рисунке в условии.