{"problem":{"name":"F. Clear The Matrix","description":{"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 (_._). You may perform the following operation arbitrary number of times: choos","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF903F"},"statements":[{"statement_type":"Markdown","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?\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint one integer — the minimum number of coins to replace all asterisks with dots.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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] 子矩阵。\n\n## Input\n\n第一行包含一个整数 #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] 的一行。每个字符要么是点，要么是星号。\n\n## Output\n\n请输出一个整数 —— 替换所有星号为点所需的最少硬币数。\n\n[samples]\n\n## Note\n\n在第一个例子中，你可以花费 #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] 子矩阵。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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} = * $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF903F","tags":["bitmasks","dp"],"sample_group":[["4\n1 10 8 20\n***.\n***.\n***.\n...*","9"],["7\n2 1 8 2\n.***...\n.***..*\n.***...\n....*..","3"],["4\n10 10 1 10\n***.\n*..*\n*..*\n.***","2"]],"created_at":"2026-03-03 11:00:39"}}