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?
## Input
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.
## Output
Print one integer — the minimum number of coins to replace all asterisks with dots.
[samples]
## Note
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.
你被给定一个矩阵 #cf_span[f]，它有 #cf_span[4] 行和 #cf_span[n] 列。矩阵的每个元素要么是星号 (_*_)，要么是点 (_._)。
你可以任意多次执行以下操作：选择一个大小为 #cf_span[k × k] 的正方形子矩阵（其中 #cf_span[1 ≤ k ≤ 4]），并将所选子矩阵中的每个元素替换为点。选择一个大小为 #cf_span[k × k] 的子矩阵需要花费 #cf_span[ak] 枚硬币。
请问，将所有星号替换为点所需的最少硬币数是多少？
第一行包含一个整数 #cf_span[n] (#cf_span[4 ≤ n ≤ 1000]) —— 矩阵 #cf_span[f] 的列数。
第二行包含 #cf_span[4] 个整数 #cf_span[a1], #cf_span[a2], #cf_span[a3], #cf_span[a4] (#cf_span[1 ≤ ai ≤ 1000]) —— 分别表示替换大小为 #cf_span[1 × 1]、#cf_span[2 × 2]、#cf_span[3 × 3] 或 #cf_span[4 × 4] 的正方形子矩阵所需的代价。
接下来四行，每行包含 #cf_span[n] 个字符，表示矩阵 #cf_span[f] 的一行。每个字符要么是点，要么是星号。
请输出一个整数 —— 替换所有星号为点所需的最少硬币数。
在第一个例子中，你可以花费 #cf_span[8] 枚硬币替换左上角的 #cf_span[3 × 3] 子矩阵，再花费 #cf_span[1] 枚硬币替换右下角的 #cf_span[1 × 1] 子矩阵。
在第二个例子中，最优方案是替换包含第 #cf_span[2 – 5] 列的 #cf_span[4 × 4] 子矩阵，以及由第 #cf_span[2 – 3] 行和第 #cf_span[6 – 7] 列组成的 #cf_span[2 × 2] 子矩阵。
在第三个例子中，你可以先选择左上角的 #cf_span[3 × 3] 子矩阵，然后选择由第 #cf_span[2 – 4] 行和第 #cf_span[2 – 4] 列组成的 #cf_span[3 × 3] 子矩阵。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[4 ≤ n ≤ 1000]) —— 矩阵 #cf_span[f] 的列数。第二行包含 #cf_span[4] 个整数 #cf_span[a1], #cf_span[a2], #cf_span[a3], #cf_span[a4] (#cf_span[1 ≤ ai ≤ 1000]) —— 分别表示替换大小为 #cf_span[1 × 1]、#cf_span[2 × 2]、#cf_span[3 × 3] 或 #cf_span[4 × 4] 的正方形子矩阵所需的代价。接下来四行，每行包含 #cf_span[n] 个字符，表示矩阵 #cf_span[f] 的一行。每个字符要么是点，要么是星号。
## Output
请输出一个整数 —— 替换所有星号为点所需的最少硬币数。
[samples]
## Note
在第一个例子中，你可以花费 #cf_span[8] 枚硬币替换左上角的 #cf_span[3 × 3] 子矩阵，再花费 #cf_span[1] 枚硬币替换右下角的 #cf_span[1 × 1] 子矩阵。在第二个例子中，最优方案是替换包含第 #cf_span[2 – 5] 列的 #cf_span[4 × 4] 子矩阵，以及由第 #cf_span[2 – 3] 行和第 #cf_span[6 – 7] 列组成的 #cf_span[2 × 2] 子矩阵。在第三个例子中，你可以先选择左上角的 #cf_span[3 × 3] 子矩阵，然后选择由第 #cf_span[2 – 4] 行和第 #cf_span[2 – 4] 列组成的 #cf_span[3 × 3] 子矩阵。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 4 \leq n \leq 1000 $, be the number of columns.
Let $ \mathbf{M} \in \{*, \cdot\}^{4 \times n} $ be the binary matrix, where $ \mathbf{M}_{i,j} = * $ indicates an asterisk and $ \mathbf{M}_{i,j} = \cdot $ indicates a dot.
Let $ a_1, a_2, a_3, a_4 \in \mathbb{Z} $, $ 1 \leq a_k \leq 1000 $, be the cost of applying a $ k \times k $ square operation.
**Constraints**
1. Only square submatrices of size $ k \times k $ for $ k \in \{1,2,3,4\} $ may be selected.
2. Each operation replaces all elements in a $ k \times k $ contiguous submatrix with dots.
3. The goal is to cover all positions $ (i,j) $ where $ \mathbf{M}_{i,j} = * $ with one or more such operations.
4. Operations may overlap.
**Objective**
Find the minimum total cost to cover all asterisks:
$$
\min \sum_{\text{operations}} a_k
$$
where each operation is a choice of top-left corner $ (i,j) $ and size $ k \in \{1,2,3,4\} $ such that the submatrix $ \mathbf{M}[i:i+k-1, j:j+k-1] $ is entirely within $ \mathbf{M} $, and the union of all covered positions includes all $ (i,j) $ with $ \mathbf{M}_{i,j} = * $.