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;
using ll = long long;
using ld = long double;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
int n;
int a[4];
string s[4];
int f[((1LL << (12)))];
int g[((1LL << (12)))];
int h[1001];
const int smax = ((1LL << (12)));
int pos[4][4];
vector<int> transforms;
vector<int> cost;
int main() {
  read(n);
  for (int i = (0); i < (4); i++) read(a[i]);
  {
    int cnt = 0;
    for (int r = (2); r >= (0); r--)
      for (int c = (0); c < (4); c++) {
        pos[r][c] = cnt;
        cnt++;
      }
  }
  for (int b = (0); b < (4); b++)
    for (int sz = (0); sz <= (b); sz++) {
      if (sz == 4) continue;
      transforms.push_back(smax - 1);
      cost.push_back(a[sz]);
      for (int c = (b - sz); c <= (b); c++)
        for (int r = (0); r <= (sz); r++)
          transforms.back() ^= ((1LL << (pos[r][c])));
    }
  for (int i = (0); i < (smax); i++) f[i] = 1e9;
  f[0] = 0;
  for (int i = (0); i < (4); i++) cin >> s[i];
  for (int r = (0); r < (n); r++) {
    int v = 0;
    for (int i = (0); i < (4); i++)
      if (s[i][r] == '*') v ^= ((1LL << (i)));
    v <<= 8;
    for (int i = (0); i < (smax); i++) {
      g[i] = f[i];
      f[i] = 1e9;
    }
    for (int i = 0; i < smax; i += ((1LL << (4)))) f[(i >> 4) | v] = g[i];
    for (int i = (smax - 1); i >= (0); i--)
      if (f[i] != 1e9)
        for (int j = (0); j < (transforms.size()); j++)
          f[i & transforms[j]] = min(f[i & transforms[j]], f[i] + cost[j]);
    f[0] = min(f[0], ((r >= 4) ? h[r - 4] : 0) + a[3]);
    h[r] = f[0];
  }
  writeln(h[n - 1]);
}
