Вам дана матрица f, состоящая из 4 строк и n столбцов. Любой элемент матрицы — либо звездочка (*), либо точка (.).
Над матрицей можно произвольное число раз производить следующую операцию: выбрать квадратную подматрицу f размера k × k (где 1 ≤ k ≤ 4) и заменить каждый элемент в выбранной подматрице на точку. Выбор подматрицы размера k × k стоит ak монет.
Какое минимальное количество монет необходимо потратить, чтобы заменить все звездочки на точки?
Выходные данные
Выведите одно целое число — минимальное количество монет, требующихся для замены всех звездочек на точки.
Примечание
В первом примере можно потратить 8 монет для замены подматрицы 3 × 3 в верхнем левом углу и 1 монету для замены подматрицы 1 × 1 в нижнем правом углу.
Во втором примере лучшим вариантом будет заменить подматрицу 4 × 4 из столбцов 2 – 5 и подматрицу 2 × 2 из строк 2 – 3 и столбцов 6 – 7.
В третьем примере можно выбрать подматрицу 3 × 3 в верхнем левом углу и подматрицу 3 × 3 из строк 2 – 4 и столбцов 2 – 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 10 8 20
***.
***.
***.
...*
|
9
|
|
2
|
7
2 1 8 2
.***...
.***..*
.***...
....*..
|
3
|
|
3
|
4
10 10 1 10
***.
*..*
*..*
.***
|
2
|