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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
void build() {}
int n, a[5];
char c[4][1021];
void init() {
  n = getint();
  for (int i = 1; i < 5; i++) a[i] = getint();
  for (int i = 0; i < 4; i++) scanf("%s", c[i] + 1);
}
unordered_map<int, int> dp[1 << 16][5];
int nmsk[1 << 16][4][5];
bool gt[1 << 16][4][5];
inline int new_mask(int ori, int who, int tk) {
  if (tk == 0) return ori;
  if (gt[ori][who][tk]) return nmsk[ori][who][tk];
  int oori = ori;
  gt[ori][who][tk] = true;
  int era = ((1 << tk) - 1) << who;
  for (int i = 0; i < tk; i++) ori &= ~(era << (i << 2));
  return nmsk[oori][who][tk] = ori;
}
int fuck[5];
void go_cal(int ori, int now, int who, int cst, int mst) {
  if (who == 4) {
    if (now >> 12) return;
    for (int i = max(1, mst); i <= 4; i++) {
      if (now >> (4 * i)) continue;
      auto it = dp[ori][i].find(now);
      if (it == dp[ori][i].end() or cst < it->second) dp[ori][i][now] = cst;
    }
    return;
  }
  for (int tk = 0; tk <= 4 - who; tk++) {
    fuck[who] = tk;
    go_cal(ori, new_mask(now, who, tk), who + 1, cst + a[tk], max(mst, tk));
  }
}
int Dp[2][1 << 12];
void solve() {
  for (int i = 0; i < (1 << 16); i++) go_cal(i, i, 0, 0, 0);
  int cur = 0, pre = 1;
  for (int msk = 0; msk < (1 << 12); msk++) Dp[cur][msk] = 1023456789LL;
  Dp[cur][0] = 0;
  for (int j = 1; j <= n; j++) {
    swap(cur, pre);
    for (int msk = 0; msk < (1 << 12); msk++) Dp[cur][msk] = 1023456789LL;
    int mst = min(4, j);
    for (int msk = 0; msk < (1 << 12); msk++) {
      if (Dp[pre][msk] == 1023456789LL) continue;
      int cmsk = msk;
      for (int i = 0; i < 4; i++) cmsk = (cmsk << 1) | (c[i][j] == '*');
      for (auto x : dp[cmsk][mst]) {
        int xmsk = x.first;
        int xcst = x.second;
        Dp[cur][xmsk] = min(Dp[cur][xmsk], Dp[pre][msk] + xcst);
      }
    }
  }
  cout << Dp[cur][0] << endl;
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}
