给定一个 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。