Ремонт#18

Ремонт

1 second
256 megabytes
Medium

Степан придбав нову квартиру і до приїзду батьків вирішив поклеїти шпалери. На перший погляд все просто, але, коли він приступив до роботи, виявилась невелика проблема – необхідно вирівнювати рисунок на сусідніх полосах шпалер. Як визнаний програміст, Степан сформулював задачу таким чином.

Кожну полосу шпалер можна описати її частиною – прямокутником довжиною і шириною (щоб отримати повну полосу, цей прямокутник можна багато разів домалювати до самого себе справа і зліва). Для простоти подумки поділимо цей прямокутник на рівні клітинки так, щоб утворилось рядків і стовпців. Щоб було ще простіше, рисунок на шпалерах позначимо символами "." і "*" (крапка і зірочка), по одному символу в кожній клітинці.

Вам дано опис двох полос шпалер. Допоможіть Степану, напишіть програму, яка визначатиме, на яку мінімальну кількість клітинок потрібно змістити другу полосу вправо, щоб її малюнок співпав з малюнком на першій полосі. Степан придбав такі шпалери, що гарантовано завжди можна це зробити.

Input

Перший рядок вхідного файлу містить два цілих числа і (1 \le N \le 20, 1 \le M \le 100000). Наступні рядків містять по символів кожна – опис першої полоси шпалер. Наступні рядків містять по символів кожна – опис другої полоси шпалер. Кожен рядок опису шпалер містить тільки символи "." і "*".

Output

Вихідний файл має містити одне число – на яку мінімальну кількість клітинок потрібно змістити другу полосу вправо, щоб її малюнок співпав з малюнком на першій полосі.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading