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, a[5];
int f[1010][1 << 12];
char s[5][1010];
vector<pair<int, int> > put[5];
vector<pair<int, int> > mov[5][1 << 4][1 << 12];
void Init() {
  scanf("%d", &n);
  for (int i = 1; i <= 4; ++i) scanf("%d", a + i);
  for (int i = 1; i <= 4; ++i) scanf("%s", s[i] + 1);
}
int modi[5][5] = {{0, 0, 0, 0, 0},
                  {0, 1, 51, 1911, 65535},
                  {0, 16, 816, 30576, 0},
                  {0, 256, 13056, 0, 0},
                  {0, 4096, 0, 0, 0}};
void DFS(int i, int fig, int cost, int sz) {
  if (i > 5) return;
  if (i == 5) {
    put[sz].push_back({fig, cost});
    return;
  }
  DFS(i + 1, fig, cost, sz);
  for (int j = 1; i + j <= 5; ++j) {
    DFS(i + 1, fig | modi[i][j], cost + a[j], max(sz, j));
  }
}
void Check(int j, int i, pair<int, int> it, int col) {
  int fi = 0, se = 0, pt;
  fi |= ((((1 << 3) - 1) << 9) & j) << 4;
  fi |= ((1 << 3) & i) << 9;
  fi |= ((((1 << 3) - 1) << 6) & j) << 3;
  fi |= ((1 << 2) & i) << 6;
  fi |= ((((1 << 3) - 1) << 3) & j) << 2;
  fi |= ((1 << 1) & i) << 3;
  fi |= (((1 << 3) - 1) & j) << 1;
  fi |= 1 & i;
  pt = fi | it.first;
  if (((pt >> 15) & 1) == 0 || ((pt >> 11) & 1) == 0 || ((pt >> 7) & 1) == 0 ||
      ((pt >> 3) & 1) == 0)
    return;
  se |= ((((1 << 3) - 1) << 12) & pt) >> 3;
  se |= ((((1 << 3) - 1) << 8) & pt) >> 2;
  se |= ((((1 << 3) - 1) << 4) & pt) >> 1;
  se |= ((1 << 3) - 1) & pt;
  mov[col][i][se].push_back({j, it.second});
}
void Work() {
  int i, j, k = 1 << 12, t = 1 << 4, col;
  for (i = 0; i < t; ++i)
    for (j = 0; j < k; ++j)
      for (col = 0; col < 5; ++col)
        for (auto &it : put[col]) Check(j, i, it, col);
  memset(f, 0x3f, sizeof(f));
  f[0][k - 1] = 0;
  for (col = 1; col <= n; ++col) {
    for (j = 1, i = 0; j <= 4; ++j) i = (i << 1) + (s[j][col] == '.');
    for (t = 0; t < 5 && t <= col; ++t) {
      for (j = 0; j < k; ++j)
        for (auto &it : mov[t][i][j]) {
          if (f[col - 1][it.first] == 0x3f3f3f3f) continue;
          f[col][j] = min(f[col][j], f[col - 1][it.first] + it.second);
        }
    }
  }
  printf("%d\n", f[n][k - 1]);
}
int main() {
  Init();
  DFS(1, 0, 0, 0);
  Work();
  return 0;
}
