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;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const long long linf = 4000000000000000000LL;
const long long inf = 998244353;
const long double pi = 3.1415926535;
void pv(vector<int> a) {
  for (auto& x : a) cout << x << " ";
  cout << '\n';
}
void pv(vector<long long> a) {
  for (auto& x : a) cout << x << " ";
  cout << '\n';
}
void pv(vector<vector<int> > a) {
  for (int i = (0); i < (int(a.size())); ++i) {
    cout << i << '\n';
    pv(a[i]);
    cout << '\n';
  }
}
void pv(vector<vector<long long> > a) {
  for (int i = (0); i < (int(a.size())); ++i) {
    cout << i << '\n';
    pv(a[i]);
  }
  cout << '\n';
}
void pv(vector<string> a) {
  for (auto& x : a) cout << x << '\n';
  cout << '\n';
}
void setIO(string second) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (int(second.size())) {
    freopen((second + ".in").c_str(), "r", stdin);
    if (second != "test1") freopen((second + ".out").c_str(), "w", stdout);
  }
}
int n;
const int SZ = 4;
int b[SZ];
string a[SZ];
const int total = 1 << SZ;
const int MAX = 1e3 + 10;
int dp[MAX][total][total][total];
int mask[MAX];
int main() {
  setIO("");
  cin >> n;
  for (int i = (0); i < (SZ); ++i) cin >> b[i];
  for (int i = (0); i < (SZ); ++i) {
    cin >> a[i];
    a[i].resize(n + 5, '.');
  }
  for (int i = (0); i < (n + 5); ++i) {
    mask[i] = 0;
    for (int j = (0); j < (SZ); ++j)
      if (a[j][i] == '.') mask[i] += (1 << j);
  }
  for (int i = (0); i < (MAX); ++i)
    for (int a = (0); a < (total); ++a)
      for (int b = (0); b < (total); ++b)
        for (int c = (0); c < (total); ++c) dp[i][a][b][c] = inf;
  dp[0][mask[0]][mask[1]][mask[2]] = 0;
  int tmask[SZ];
  int m[SZ];
  for (int cur = (0); cur < (n); ++cur) {
    for (int mask1 = (0); mask1 < (total); ++mask1) {
      for (int mask2 = (0); mask2 < (total); ++mask2) {
        for (int mask3 = (0); mask3 < (total); ++mask3) {
          if (dp[cur][mask1][mask2][mask3] == inf) continue;
          for (m[0] = 0; m[0] < 16; m[0]++) {
            if (m[0] && cur + 0 >= n) continue;
            for (m[1] = 0; m[1] < 8; m[1]++) {
              if (m[1] && cur + 1 >= n) continue;
              for (m[2] = 0; m[2] < 4; m[2]++) {
                if (m[2] && cur + 2 >= n) continue;
                for (m[3] = 0; m[3] < 2; m[3]++) {
                  if (m[3] && cur + 3 >= n) continue;
                  tmask[0] = mask1;
                  tmask[1] = mask2;
                  tmask[2] = mask3;
                  tmask[3] = mask[cur + 3];
                  int cost = 0;
                  for (int size = (0); size < (SZ); ++size) {
                    int len = SZ - size;
                    for (int i = (0); i < (len); ++i) {
                      if (m[size] & (1 << i)) {
                        cost += b[size];
                        for (int k = (0); k < (size + 1); ++k) {
                          for (int l = (0); l < (size + 1); ++l) {
                            tmask[k] |= 1 << l + i;
                          }
                        }
                      }
                    }
                  }
                  if (tmask[0] == total - 1)
                    dp[cur + 1][tmask[1]][tmask[2]][tmask[3]] =
                        min(dp[cur + 1][tmask[1]][tmask[2]][tmask[3]],
                            dp[cur][mask1][mask2][mask3] + cost);
                }
              }
            }
          }
        }
      }
    }
  }
  cout << dp[n][total - 1][total - 1][total - 1] << '\n';
}
