F. Замена подматриц
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана матрица f, состоящая из 4 строк и n столбцов. Любой элемент матрицы — либо звездочка (*), либо точка (.).

Над матрицей можно произвольное число раз производить следующую операцию: выбрать квадратную подматрицу f размера k × k (где 1 ≤ k ≤ 4) и заменить каждый элемент в выбранной подматрице на точку. Выбор подматрицы размера k × k стоит ak монет.

Какое минимальное количество монет необходимо потратить, чтобы заменить все звездочки на точки?

Входные данные

В первой строке записано одно целое число n (4 ≤ n ≤ 1000) — количество столбцов в f.

Во второй строке записаны 4 целых числа a1, a2, a3, a4 (1 ≤ ai ≤ 1000) — цена замены квадратных подматриц размеров 1 × 1, 2 × 2, 3 × 3 и 4 × 4, соответственно.

Затем идет четыре строки, в каждой по n символов, обозначающие строки матрицы f. Любой символ — либо точка, либо звездочка.

Выходные данные

Выведите одно целое число — минимальное количество монет, требующихся для замены всех звездочек на точки.

Примеры
Входные данные
4
1 10 8 20
***.
***.
***.
...*
Выходные данные
9
Входные данные
7
2 1 8 2
.***...
.***..*
.***...
....*..
Выходные данные
3
Входные данные
4
10 10 1 10
***.
*..*
*..*
.***
Выходные данные
2
Примечание

В первом примере можно потратить 8 монет для замены подматрицы 3 × 3 в верхнем левом углу и 1 монету для замены подматрицы 1 × 1 в нижнем правом углу.

Во втором примере лучшим вариантом будет заменить подматрицу 4 × 4 из столбцов 2 – 5 и подматрицу 2 × 2 из строк 2 – 3 и столбцов 6 – 7.

В третьем примере можно выбрать подматрицу 3 × 3 в верхнем левом углу и подматрицу 3 × 3 из строк 2 – 4 и столбцов 2 – 4.