Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Clear The Matrix

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 *a*_{k} 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 *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.

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

Input

4

1 10 8 20

***.

***.

***.

...*

Output

9

Input

7

2 1 8 2

.***...

.***..*

.***...

....*..

Output

3

Input

4

10 10 1 10

***.

*..*

*..*

.***

Output

2

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/23/2018 20:35:07 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|