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;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int a[5];
char s[4][1011];
int dp[1011][256];
int st[4], nst[4];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= 4; i++) scanf("%d", a + i);
  for (int i = 0; i < 4; i++) scanf("%s", s[i] + 1);
  for (int i = 0; i <= n; i++)
    for (int j = 0; j < 256; j++) dp[i][j] = 0x3f3f3f3f;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 256; j++) {
      int jj = j;
      for (int k = 0; k < 4; k++) st[k] = jj % 4, jj /= 4;
      for (int a1 = 0; a1 <= 4; a1++) {
        for (int a2 = 0; a2 <= 3; a2++) {
          for (int a3 = 0; a3 <= 2; a3++) {
            for (int a4 = 0; a4 <= 1; a4++) {
              for (int k = 0; k < 4; k++) nst[k] = st[k];
              for (int k = 0; k < a1; k++) smax(nst[k], a1);
              for (int k = 1; k < 1 + a2; k++) smax(nst[k], a2);
              for (int k = 2; k < 2 + a3; k++) smax(nst[k], a3);
              smax(nst[3], a4);
              int f = 0;
              for (int k = 0; k < 4; k++) {
                nst[k]--;
                if (nst[k] < 0) {
                  if (s[k][i] == '*')
                    f = 1;
                  else
                    nst[k] = 0;
                }
              }
              if (f) continue;
              int val = 0;
              for (int k = 3; k >= 0; k--) val = val * 4 + nst[k];
              smin(dp[i][val], dp[i - 1][j] + a[a1] + a[a2] + a[a3] + a[a4]);
            }
          }
        }
      }
    }
  }
  int ans = 0x3f3f3f3f;
  for (int i = 0; i < 256; i++) smin(ans, dp[n][i]);
  cout << ans << endl;
  return 0;
}
