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;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr), ios::sync_with_stdio(false),
        cout << fixed << setprecision(20);
  };
} fast_ios_;
template <class T>
auto add = [](T a, T b) -> T { return a + b; };
template <class T>
auto f_max = [](T a, T b) -> T { return max(a, b); };
template <class T>
auto f_min = [](T a, T b) -> T { return min(a, b); };
template <class T>
using V = vector<T>;
using Vl = V<long long int>;
using VVl = V<Vl>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long int ceil(long long int a, long long int b) { return (a + b - 1) / b; }
long long int digit(long long int a) { return (long long int)log10(a); }
long long int e_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) * abs(a.first - b.first) +
         abs(a.second - b.second) * abs(a.second - b.second);
}
long long int m_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}
bool check_overflow(long long int a, long long int b, long long int limit) {
  return a > limit / b;
}
void Worshall_Floyd(VVl& g) {
  for (long long int k = (0), k_end_ = (((long long int)(g).size()));
       k < k_end_; ++k)
    for (long long int i = (0), i_end_ = (((long long int)(g).size()));
         i < i_end_; ++i)
      for (long long int j = (0), j_end_ = (((long long int)(g).size()));
           j < j_end_; ++j)
        chmin(g[i][j], g[i][k] + g[k][j]);
}
const long long int MOD1000000007 = 1000000007, MOD998244353 = 998244353,
                    INF = 5e18;
long long int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1},
              dy[8] = {0, 1, 0, -1, -1, -1, 1, 1};
bool YN(bool flag) {
  cout << (flag ? "YES" : "NO") << '\n';
  return flag;
}
bool yn(bool flag) {
  cout << (flag ? "Yes" : "No") << '\n';
  return flag;
}
struct Edge {
  long long int from, to;
  long long int cost;
  Edge() {}
  Edge(long long int u, long long int v, long long int c) {
    cost = c;
    from = u;
    to = v;
  }
  bool operator<(const Edge& e) const { return cost < e.cost; }
};
struct WeightedEdge {
  long long int to;
  long long int cost;
  WeightedEdge(long long int v, long long int c = 1) {
    to = v;
    cost = c;
  }
  bool operator<(const WeightedEdge& e) const { return cost < e.cost; }
};
using WeightedGraph = V<V<WeightedEdge>>;
long long int N;
int main() {
  cin >> N;
  Vl cost(4);
  cin >> cost;
  V<string> arr(4);
  cin >> arr;
  VVl dp(N + 1, Vl(1 << 12, INF));
  long long int init = 0;
  for (long long int i = (0), i_end_ = (3); i < i_end_; ++i) {
    for (long long int j = (0), j_end_ = (4); j < j_end_; ++j) {
      init |= ((arr[j][i] == '*') << (i * 4 + j));
    }
  }
  dp[0][init] = 0;
  for (long long int i = (0), i_end_ = (N); i < i_end_; ++i) {
    for (long long int mask = (0), mask_end_ = (1 << 12); mask < mask_end_;
         ++mask) {
      if (dp[i][mask] == INF) continue;
      long long int tmp = 0;
      if (i + 3 < N) {
        for (long long int j = (0), j_end_ = (4); j < j_end_; ++j) {
          tmp |= ((arr[j][i + 3] == '*') << (8 + j));
        }
      }
      for (long long int p1 = (0), p1_end_ = (5); p1 < p1_end_; ++p1) {
        for (long long int p2 = (0), p2_end_ = (4); p2 < p2_end_; ++p2) {
          for (long long int p3 = (0), p3_end_ = (3); p3 < p3_end_; ++p3) {
            for (long long int p4 = (0), p4_end_ = (2); p4 < p4_end_; ++p4) {
              long long int nxt = 0b111111111111, curr = 0b1111;
              if (p1 == 1) curr &= 0b1110;
              if (p1 == 2) nxt &= 0b111111111100, curr &= 0b1100;
              if (p1 == 3) nxt &= 0b111110001000, curr &= 0b1000;
              if (p1 == 4) nxt &= 0b000000000000, curr &= 0b0000;
              if (p2 == 1) curr &= 0b1101;
              if (p2 == 2) nxt &= 0b111111111001, curr &= 0b1001;
              if (p2 == 3) nxt &= 0b111100010001, curr &= 0b0001;
              if (p3 == 1) curr &= 0b1011;
              if (p3 == 2) nxt &= 0b111111110011, curr &= 0b0011;
              if (p4 == 1) curr &= 0b0111;
              long long int _nxt = mask >> 4, _curr = mask & 0b1111;
              _nxt |= tmp;
              if ((_curr & curr) != 0) continue;
              long long int _cost = 0;
              if (p1 != 0) _cost += cost[p1 - 1];
              if (p2 != 0) _cost += cost[p2 - 1];
              if (p3 != 0) _cost += cost[p3 - 1];
              if (p4 != 0) _cost += cost[p4 - 1];
              chmin(dp[i + 1][nxt & _nxt], dp[i][mask] + _cost);
            }
          }
        }
      }
    }
  }
  cout << *min_element((dp[N]).begin(), (dp[N]).end()) << '\n';
}
