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 maxN = 1010;
const int inf = 999999999;
const int shift = 16;
char m[4][maxN];
int v[4][maxN];
int dp[maxN][1 << shift];
int cost[4];
int status[maxN][4];
int mask_table[4][4];
vector<int> choice;
void gen_mask_table() {
  int cnt = 0;
  for (int j = 0; j < 4; j++) {
    for (int i = 0; i < 4; i++) {
      mask_table[i][j] = 1 << (cnt++);
    }
  }
}
void gen_mask(int n) {
  for (int i = 0; i < n + 4; i++) {
    for (int j = 0; j < 4; j++) {
      status[i][j] = 0;
      for (int k = i; k <= i + j; k++) {
        for (int t = 0; t < 4; t++) {
          status[i][j] += v[t][k] * mask_table[t][k - i];
        }
      }
    }
  }
}
vector<int> fee;
void gen_choice() {
  for (int sz = 1; sz <= 4; sz++) {
    for (int lx = 0; lx <= 4 - sz; lx++) {
      for (int ly = 0; ly <= 0; ly++) {
        int ans = 0;
        for (int i = lx; i < lx + sz; i++) {
          for (int j = ly; j < ly + sz; j++) {
            ans += mask_table[i][j];
          }
        }
        choice.push_back(ans);
        fee.push_back(cost[sz - 1]);
      }
    }
  }
}
int visit[1 << shift];
void bfs(int i) {
  priority_queue<pair<int, int>, vector<pair<int, int> >,
                 greater<pair<int, int> > >
      Q;
  for (int stat = 0; stat < (1 << shift); stat++) {
    if (dp[i][stat] < inf) {
      Q.push(make_pair(dp[i][stat], stat));
    }
  }
  while (Q.size()) {
    pair<int, int> stat_top = Q.top();
    Q.pop();
    int score = stat_top.first;
    int stat = stat_top.second;
    if (dp[i][stat] < score) continue;
    for (int t = 0; t < choice.size(); t++) {
      int son = ((~choice[t]) & stat);
      if (son != stat) {
        if (dp[i][son] > dp[i][stat] + fee[t]) {
          dp[i][son] = dp[i][stat] + fee[t];
          Q.push(make_pair(dp[i][son], son));
        }
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < 4; i++) {
    scanf("%d", &cost[i]);
  }
  for (int i = 0; i < 4; i++) {
    scanf("%s", m[i]);
    for (int j = 0; j < n; j++) {
      v[i][j] = (m[i][j] == '*');
    }
  }
  gen_mask_table();
  gen_mask(n + 4);
  gen_choice();
  for (int i = 0; i < maxN; i++) {
    for (int j = 0; j < (1 << shift); j++) {
      dp[i][j] = inf;
    }
  }
  dp[0][status[0][3]] = 0;
  for (int i = 0; i < n; i++) {
    bfs(i);
    for (int pos = 0; pos < (1 << shift); pos++) {
      if (pos % 16 == 0) {
        int nstat = pos / 16 + status[i + 4][0] * 256 * 16;
        dp[i + 1][nstat] = min(dp[i][pos], dp[i + 1][nstat]);
      }
      if (pos % 256 == 0) {
        int nstat = pos / 256 + status[i + 4][1] * 256;
        dp[i + 2][nstat] = min(dp[i][pos], dp[i + 2][nstat]);
      }
      if (i == 0 && pos % 4096 == 0) {
        int nstat = pos / 4096 + status[i + 4][2] * 16;
        dp[i + 3][nstat] = min(dp[i][pos], dp[i + 3][nstat]);
      }
      if (pos == 0) {
        int nstat = status[i + 4][3];
        dp[i + 4][nstat] = min(dp[i][pos], dp[i + 4][nstat]);
      }
    }
  }
  cout << dp[n - 1][0] << endl;
  return 0;
}
