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 a1, a2, a3, a4 (1 ≤ ai ≤ 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.
#include <bits/stdc++.h>
using namespace std;
int n, v1, v2, v3, v4, bin[25];
int line[1010], cnt[20];
char str[1010];
map<int, int> f[1010];
inline int min(int a, int b) { return a < b ? a : b; }
inline void print4(int s) {
  for (register int i = 3; ~i; --i) printf("%d", (s >> i) & 1);
  printf("\n");
}
inline void print16(int s) {
  for (register int i = 15; ~i; --i) printf("%d", (s >> i) & 1);
  printf("\n");
}
struct opt {
  int val, s;
};
vector<opt> can[20];
inline int calc(int cur, int state) {
  if (cur > n) return 0;
  if (f[cur].count(state)) return f[cur][state];
  int s = state >> 12;
  if (!s)
    return f[cur][state] =
               calc(cur + 1, 65535 & ((state << 4) | line[cur + 4]));
  int ret = 0x3f3f3f3f;
  for (vector<opt>::iterator it = can[s].begin(); it != can[s].end(); ++it)
    ret = min(ret, it->val + calc(cur + 1, ((65535 & ((it->s & state) << 4)) |
                                            line[cur + 4])));
  return f[cur][state] = ret;
}
int mayb[15] = {0,     0,     34959, 4383,  39423, 52479,
                13311, 32767, 49151, 57343, 61439},
    valb[15];
inline void dfs(int st, int state, int val) {
  if (st > 10) {
    register int i, ss = state >> 12;
    for (i = 1; i < 16; ++i)
      if ((ss & i) == 0) can[i].push_back((opt){val, state});
    return;
  }
  dfs(st + 1, state, val);
  if ((state & mayb[st]) != state)
    dfs(st + 1, state & mayb[st], val + valb[st]);
}
int main() {
  register int i, j, to;
  for (bin[0] = i = 1; i <= 20; ++i) bin[i] = bin[i - 1] << 1;
  scanf("%d%d%d%d%d", &n, &v1, &v2, &v3, &v4);
  valb[1] = v4, valb[2] = valb[3] = v3, valb[4] = valb[5] = valb[6] = v2,
  valb[7] = valb[8] = valb[9] = valb[10] = v1;
  dfs(1, 65535, 0);
  for (i = 1; i < 16; ++i) cnt[i] = cnt[i ^ (i & (-i))] + 1;
  for (i = 0; i < 4; ++i)
    for (scanf("%s", str + 1), j = 1; j <= n; ++j)
      if (str[j] == '*') line[j] |= (1 << i);
  printf("%d\n",
         calc(1, (line[1] << 12) | (line[2] << 8) | (line[3] << 4) | line[4]));
}
