Clear The Matrix

题目描述 给定一个4×n的元素只为'*'或'.'的矩阵f 你可以不断地选择一个f的子方阵,并将方阵的元素都变为'.' 选择一个k×k的方阵需要代价$a_k$​。 问最少要多少代价,才能将所有元素都变为'.' 输入输出格式 输入格式： 第一行包含一个整数n——矩阵f中的列数 第二行包含四个整数$a_1,a_2,a_3,a_4(1≤a_i≤1000)$分别为覆盖一个1×1,2×2,3×3,4×4子矩阵的成本 接下来的四行，每行包含n个字符，表示矩阵f中的一行，每个字符均为'.'或者'*' 输出格式： 输出一个整数——用原矩阵所有元素变为'.'的最小成本 Translated by League丶翎

You are given a matrix $ f $ with $ 4 $ rows and $ n $ columns. Each element of the matrix is either an asterisk (\*) or a dot (.). You may perform the following operation arbitrary number of times: choose a square submatrix of $ f $ with size $ k×k $ (where $ 1<=k<=4 $ ) and replace each element of the chosen submatrix with a dot. Choosing a submatrix of size $ k×k $ costs $ a_{k} $ coins. What is the minimum number of coins you have to pay to replace all asterisks with dots?

The first line contains one integer $ n $ ( $ 4<=n<=1000 $ ) — the number of columns in $ f $ . The second line contains $ 4 $ integers $ a_{1} $ , $ a_{2} $ , $ a_{3} $ , $ a_{4} $ ( $ 1<=a_{i}<=1000 $ ) — the cost to replace the square submatrix of size $ 1×1 $ , $ 2×2 $ , $ 3×3 $ or $ 4×4 $ , respectively. Then four lines follow, each containing $ n $ characters and denoting a row of matrix $ f $ . Each character is either a dot or an asterisk.

Print one integer — the minimum number of coins to replace all asterisks with dots.

4
1 10 8 20
***.
***.
***.
...*

9

7
2 1 8 2
.***...
.***..*
.***...
....*..

3

4
10 10 1 10
***.
*..*
*..*
.***

2

In the first example you can spend $ 8 $ coins to replace the submatrix $ 3×3 $ in the top-left corner, and $ 1 $ coin to replace the $ 1×1 $ submatrix in the bottom-right corner. In the second example the best option is to replace the $ 4×4 $ submatrix containing columns $ 2–5 $ , and the $ 2×2 $ submatrix consisting of rows $ 2–3 $ and columns $ 6–7 $ . In the third example you can select submatrix $ 3×3 $ in the top-left corner and then submatrix $ 3×3 $ consisting of rows $ 2–4 $ and columns $ 2–4 $ .