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, f[1100][100], a[5], t[5], u[5], q[5], w[5], mi[5];
const int INF = 0x3f3f3f3f;
char s[5][1100];
void dfs(int v, int k, int cost, int p) {
  if (k > 4) {
    for (int i = 1; i <= 4; i++) u[i] = q[i];
    for (int i = 1; i <= 4; i++) {
      if (w[i] == 2) {
        u[i] = max(u[i], 1);
        u[i + 1] = max(u[i + 1], 1);
      }
      if (w[i] == 3) u[i] = u[i + 1] = u[i + 2] = 2;
    }
    int t = 0;
    for (int i = 1; i <= 4; i++) t = t + u[i] * mi[i - 1];
    f[v + 1][t] = min(f[v + 1][t], cost);
    return;
  }
  w[k] = 1;
  dfs(v, k + 1, cost + a[1], p | (1 << (k - 1)));
  if (((1 << (k - 1)) & p) > 0) {
    w[k] = 0;
    dfs(v, k + 1, cost, p);
  }
  if (k < 4) {
    w[k] = 2;
    dfs(v, k + 1, cost + a[2], p | (1 << (k - 1)) | (1 << k));
  }
  if (k < 3) {
    w[k] = 3;
    dfs(v, k + 1, cost + a[3], p | (1 << (k - 1)) | (1 << k) | (1 << (k + 1)));
  }
}
int main() {
  mi[0] = 1;
  mi[1] = 3;
  mi[2] = 9;
  mi[3] = 27;
  cin >> n >> a[1] >> a[2] >> a[3] >> a[4];
  cin >> s[1] + 1 >> s[2] + 1 >> s[3] + 1 >> s[4] + 1;
  s[1][n + 1] = s[2][n + 1] = s[3][n + 1] = s[4][n + 1] = '.';
  memset(f, 0x3f, sizeof(f));
  f[1][0] = 0;
  int ans = INF;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= 80; j++) {
      if (f[i][j] == INF) continue;
      int p = (1 << 4) - 1, o = j;
      for (int k = 1; k <= 4; k++) {
        t[k] = o % 3;
        o = o / 3;
        if (t[k] == 0 && s[k][i] == '*') p = p - (1 << (k - 1));
        if (t[k] == 2)
          q[k] = 1;
        else
          q[k] = 0;
      }
      dfs(i, 1, f[i][j], p);
      f[i + 2][80] = min(f[i + 2][80], f[i][j] + a[4]);
      if (i + 2 >= n - 1) ans = min(ans, f[i + 2][80]);
    }
  for (int i = 0; i <= 80; i++) ans = min(ans, f[n + 1][i]);
  cout << ans;
  return 0;
}
