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 N = 1000 + 5;
int n;
int cost[5];
char s[4][N];
int a[4][N];
bool prevMark[1 << 9];
int prevCost[1 << 9];
bool nextMark[(1 << 9)];
int nextCost[(1 << 9)];
int go[(1 << 8)][(1 << 4)][150];
int goCost[(1 << 8)][(1 << 4)][150];
int topGo[(1 << 8)][(1 << 4)];
int c[4][4];
int nc[4][4];
int used[(1 << 9)];
int taken[(1 << 9)];
int precCost[(1 << 9)];
int squres[150][4];
int posGo[150];
void precalc() {
  int squreSize = 0;
  for (int i = 0; i <= 3; ++i) {
    for (int j = 0; j <= 3; ++j) {
      for (int u = 0; u <= 2; ++u) {
        for (int v = 0; v <= 1; ++v) {
          squres[squreSize][0] = i;
          squres[squreSize][1] = j;
          squres[squreSize][2] = u;
          squres[squreSize][3] = v;
          ++squreSize;
        }
      }
    }
  }
  int crUsed = 0;
  for (int prev = 0; prev < (1 << 8); ++prev) {
    for (int col = 0; col < (1 << 4); ++col) {
      ++crUsed;
      int top = 0;
      int mask = prev + (col << 8);
      for (int j = 0; j < 3; ++j) {
        for (int i = 0; i < 4; ++i) {
          c[i][j] = (bool)(mask & (1 << top));
          top++;
        }
      }
      int goTop = 0;
      for (int ind = 0; ind < squreSize; ++ind) {
        for (int j = 0; j < 3; ++j) {
          for (int i = 0; i < 4; ++i) {
            nc[i][j] = c[i][j];
          }
        }
        int addCost = 0;
        for (int i = 0; i < 4; ++i) {
          int sq = squres[ind][i];
          addCost += cost[sq];
          int i1 = i, i2 = i + sq - 1;
          int j1 = 2 - sq + 1, j2 = 2;
          for (int u = i1; u <= i2; ++u) {
            for (int v = j1; v <= j2; ++v) {
              nc[u][v] = 0;
            }
          }
        }
        top = 0;
        int newMask = 0;
        for (int j = 1; j < 3; ++j) {
          for (int i = 0; i < 4; ++i) {
            newMask |= nc[i][j] * (1 << top);
            ++top;
          }
        }
        for (int i = 0; i < 4; ++i) {
          newMask |= nc[i][0] * (1 << top);
        }
        if (used[newMask] != crUsed || precCost[newMask] > addCost) {
          used[newMask] = crUsed;
          precCost[newMask] = addCost;
          posGo[goTop++] = newMask;
        }
      }
      for (int g = 0; g < goTop; ++g) {
        int newMask = posGo[g];
        int addCost = precCost[newMask];
        if (taken[newMask] == crUsed) {
          continue;
        }
        taken[newMask] = crUsed;
        int in = topGo[prev][col];
        go[prev][col][in] = newMask;
        goCost[prev][col][in] = addCost;
        ++topGo[prev][col];
      }
    }
  }
}
int possible[12];
int cur[12];
void update(int mask, int val) {
  if (!nextMark[mask] || nextCost[mask] > val) {
    nextMark[mask] = true;
    nextCost[mask] = val;
  }
}
void solve() {
  scanf("%d", &n);
  for (int i = 1; i <= 4; ++i) {
    scanf("%d", &cost[i]);
  }
  for (int i = 0; i < 4; ++i) {
    scanf("%s", s[i]);
  }
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < n; ++j) {
      a[i][j] = (bool)(s[i][j] == '*');
    }
  }
  precalc();
  int top = 0;
  for (int j = 0; j < 3; ++j) {
    for (int i = 0; i < 4; ++i) {
      int sq = min(4 - i, j + 1);
      possible[top++] = sq;
    }
  }
  for (int i = 0; i < top; ++i) {
    cur[i] = 0;
  }
  do {
    bool ok = false;
    for (int i = 0; i < top; ++i) {
      if (cur[i] != possible[i]) {
        ok = true;
        break;
      }
    }
    if (!ok) {
      break;
    }
    for (int j = 0; j < 3; ++j) {
      for (int i = 0; i < 4; ++i) {
        c[i][j] = a[i][j];
      }
    }
    int addCost = 0;
    int sh = 0;
    for (int j = 0; j < 3; ++j) {
      for (int i = 0; i < 4; ++i) {
        int sq = cur[sh++];
        addCost += cost[sq];
        int i1 = i, i2 = i + sq - 1;
        int j1 = j - sq + 1, j2 = j;
        for (int u = i1; u <= i2; ++u) {
          for (int v = j1; v <= j2; ++v) {
            c[u][v] = 0;
          }
        }
      }
    }
    sh = 0;
    int newMask = 0;
    for (int j = 1; j < 3; ++j) {
      for (int i = 0; i < 4; ++i) {
        newMask |= c[i][j] * (1 << sh);
        sh++;
      }
    }
    for (int i = 0; i < 4; ++i) {
      newMask |= c[i][0] * (1 << sh);
    }
    if (!prevMark[newMask] || prevCost[newMask] > addCost) {
      prevCost[newMask] = addCost;
      prevMark[newMask] = true;
    }
    int i = 0;
    while (cur[i] == possible[i]) {
      cur[i] = 0;
      ++i;
    }
    ++cur[i];
  } while (1);
  for (int j = 3; j < n; ++j) {
    for (int mask = 0; mask < (1 << 9); ++mask) {
      nextCost[mask] = 0;
      nextMark[mask] = false;
    }
    int col = 0;
    for (int i = 0; i < 4; ++i) {
      col |= a[i][j] * (1 << i);
    }
    for (int prev = 0; prev < (1 << 9); ++prev) {
      if (!prevMark[prev]) {
        continue;
      }
      bool need4 = (bool)(prev & (1 << 8));
      int last3 = prev ^ (prev & (1 << 8));
      if (need4) {
        update(0, cost[4] + prevCost[prev]);
      } else {
        update(0, cost[4] + prevCost[prev]);
        for (int gin = 0; gin < topGo[prev][col]; ++gin) {
          update(go[prev][col][gin], prevCost[prev] + goCost[prev][col][gin]);
        }
      }
    }
    for (int mask = 0; mask < (1 << 9); ++mask) {
      prevCost[mask] = nextCost[mask];
      prevMark[mask] = nextMark[mask];
    }
  }
  printf("%d\n", prevCost[0]);
}
int main() {
  solve();
  return 0;
}
