CF903F Clear The Matrix

给定一个 $4\times n$ 的元素只为 `*` 或 `.` 的矩阵 $f$。 你可以不断地选择一个 $f$ 的子方阵，并将方阵的元素都变为 `.`。 选择一个 $k \times k$ 的方阵需要代价 $a_k$。 问最少要多少代价，才能将所有元素都变为 `.`。

第一行包含一个整数 $n$（$4 \le n \le 1000$）——矩阵 $f$ 中的列数。 第二行包含四个整数 $a_1,a_2,a_3,a_4$（$1 \le a_i \le 1000$）分别为覆盖一个 $1 \times 1, 2 \times 2, 3 \times 3, 4 \times 4$ 子矩阵的成本。 接下来的四行，每行包含 $n$ 个字符，表示矩阵 $f$ 中的一行，每个字符均为 `.` 或者 `*`。

输出一个整数——用原矩阵所有元素变为 `.` 的最小成本。

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 $ .