← 返回题目列表

Codeforces · 903/F

F. 清除矩阵

中文机器翻译题面 查看原题

给定一个 4 行 n 列的矩阵 f 。矩阵的每个元素都是星号 (*) 或点 (.)。

您可以执行任意次数的以下操作:选择大小为 k × k(其中 1 ≤ k ≤ 4)的 f 方子矩阵,并用点替换所选子矩阵的每个元素。选择大小为 k × k 的子矩阵需要花费 ak 个硬币。

要将所有星号替换为点,您至少需要支付多少硬币?

输入

第一行包含一个整数 n (4 ≤ n ≤ 1000) — f 中的列数。

第二行包含 4 个整数 a1、a2、a3、a4 (1 ≤ ai ≤ 1000) — 分别替换大小为 1 × 1、2 × 2、3 × 3 或 4 × 4 的方形子矩阵的成本。

接下来是四行,每行包含 n 个字符并表示矩阵 f 的一行。每个字符都是一个点或一个星号。

输出

打印一个整数 — 将所有星号替换为点的最小硬币数量。

示例

输入 #1

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

输出 #1

9

输入 #2

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

输出 #2

3

输入 #3

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

输出 #3

2

注意

在第一个示例中,您可以花费 8 个硬币来替换左上角的 3 × 3 子矩阵,并花费 1 个硬币来替换右下角的 1 × 1 子矩阵。

在第二个示例中,最佳选择是替换包含第 2 – 5 列的 4 × 4 子矩阵以及包含第 2 – 3 行和第 6 – 7 列的 2 × 2 子矩阵。

在第三个示例中,您可以选择左上角的子矩阵 3 × 3,然后选择由第 2 – 4 行和第 2 – 4 列组成的子矩阵 3 × 3。