{"raw_statement":[{"iden":"statement","content":"You are given a matrix _f_ with 4 rows and _n_ columns. Each element of the matrix is either an asterisk (_*_) or a dot (_._).\n\nYou 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.\n\nWhat is the minimum number of coins you have to pay to replace all asterisks with dots?"},{"iden":"input","content":"The first line contains one integer _n_ (4 ≤ _n_ ≤ 1000) — the number of columns in _f_.\n\nThe 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.\n\nThen four lines follow, each containing _n_ characters and denoting a row of matrix _f_. Each character is either a dot or an asterisk."},{"iden":"output","content":"Print one integer — the minimum number of coins to replace all asterisks with dots."},{"iden":"examples","content":"Input\n\n4\n1 10 8 20\n***.\n***.\n***.\n...*\n\nOutput\n\n9\n\nInput\n\n7\n2 1 8 2\n.***...\n.***..*\n.***...\n....*..\n\nOutput\n\n3\n\nInput\n\n4\n10 10 1 10\n***.\n*..*\n*..*\n.***\n\nOutput\n\n2"},{"iden":"note","content":"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.\n\nIn 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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"你被给定一个矩阵 #cf_span[f]，它有 #cf_span[4] 行和 #cf_span[n] 列。矩阵的每个元素要么是星号 (_*_)，要么是点 (_._)。\n\n你可以任意多次执行以下操作：选择一个大小为 #cf_span[k × k] 的正方形子矩阵（其中 #cf_span[1 ≤ k ≤ 4]），并将所选子矩阵中的每个元素替换为点。选择一个大小为 #cf_span[k × k] 的子矩阵需要花费 #cf_span[ak] 枚硬币。\n\n请问，将所有星号替换为点所需的最少硬币数是多少？\n\n第一行包含一个整数 #cf_span[n] (#cf_span[4 ≤ n ≤ 1000]) —— 矩阵 #cf_span[f] 的列数。\n\n第二行包含 #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] 的正方形子矩阵所需的代价。\n\n接下来四行，每行包含 #cf_span[n] 个字符，表示矩阵 #cf_span[f] 的一行。每个字符要么是点，要么是星号。\n\n请输出一个整数 —— 替换所有星号为点所需的最少硬币数。\n\n在第一个例子中，你可以花费 #cf_span[8] 枚硬币替换左上角的 #cf_span[3 × 3] 子矩阵，再花费 #cf_span[1] 枚硬币替换右下角的 #cf_span[1 × 1] 子矩阵。\n\n在第二个例子中，最优方案是替换包含第 #cf_span[2 – 5] 列的 #cf_span[4 × 4] 子矩阵，以及由第 #cf_span[2 – 3] 行和第 #cf_span[6 – 7] 列组成的 #cf_span[2 × 2] 子矩阵。\n\n在第三个例子中，你可以先选择左上角的 #cf_span[3 × 3] 子矩阵，然后选择由第 #cf_span[2 – 4] 行和第 #cf_span[2 – 4] 列组成的 #cf_span[3 × 3] 子矩阵。"},{"iden":"input","content":"第一行包含一个整数 #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] 的一行。每个字符要么是点，要么是星号。"},{"iden":"output","content":"请输出一个整数 —— 替换所有星号为点所需的最少硬币数。"},{"iden":"examples","content":"输入\n4\n1 10 8 20\n***.\n***.\n***.\n....\n输出\n9\n\n输入\n7\n2 1 8 2\n.***...\n***..*.\n***....\n...*..\n输出\n3\n\n输入\n4\n10 10 1 10\n***.\n*..*\n**..\n*.**\n输出\n2"},{"iden":"note","content":"在第一个例子中，你可以花费 #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] 子矩阵。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 4 \\leq n \\leq 1000 $, be the number of columns.  \nLet $ \\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.  \nLet $ 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.\n\n**Constraints**  \n1. Only square submatrices of size $ k \\times k $ for $ k \\in \\{1,2,3,4\\} $ may be selected.  \n2. Each operation replaces all elements in a $ k \\times k $ contiguous submatrix with dots.  \n3. The goal is to cover all positions $ (i,j) $ where $ \\mathbf{M}_{i,j} = * $ with one or more such operations.  \n4. Operations may overlap.\n\n**Objective**  \nFind the minimum total cost to cover all asterisks:  \n$$\n\\min \\sum_{\\text{operations}} a_k\n$$  \nwhere 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} = * $.","simple_statement":null,"has_page_source":false}