Codeforces 903F. Clear The Matrix

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 ak 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 a1a2a3a4 (1 ≤ ai ≤ 1000) — the cost to replace the square submatrix of size 1 × 12 × 23 × 3or 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.

Examples

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.

题意简述

有一个 $4\times n$ 的矩阵,矩阵中有一些点需要清除。有四种清除方式——第 $i$ 种为把一个 $i\times i$ 的子矩阵里的点都清除。每种清除方式有不同的代价。求将所有该清除的点都清除需要花费的最小代价。

分析

一开始想的是状态 $f(i, \cdots )$ 表示所有子矩阵都摆在前 $i$ 列,再满足一些其他条件时最小代价,之所以是都摆在前 $i$ 列是为了方便满足后效性。然后发现状态怎么设计都找不到较优的解决方案。

考虑将第一维放宽一些,用 $f(i, \cdots )$ 表示所有子矩阵的左上角都在前 $i$ 列,再满足其他一些条件的最小代价。这样设计状态不方便满足后效性,因为有一些不在前 $i$ 列的点也被清除了,对我们在之后摆放矩阵的方式会有一定影响。可以考虑如何消除后效性,也就是如何增加一些状态来记录后面的点是否被清除。

显然,当所有子矩阵的左上角都在前 $i$ 列时,超出前 $i$ 列最多覆盖 3 列,因此可以设计状态 $f(i, k_0, k_1, k_2, k_3)$ 表示所有子矩阵的左上角都在前 $i$ 列,已经清除前 $i$ 列所有点,且四行各多向右覆盖 $k_0, k_1, k_2, k_3$ 个格子的最小代价。

转移就只要枚举所有在这一列上摆放格子的方案即可。

(通过预处理可以有效地提升效率并使代码更有条理)

 

发表评论