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 MAX_N = 1010, B = (1 << 4) + 1;
int n, a[5], col[MAX_N];
int memo[B][B][B][MAX_N];
vector<string> mat(4);
int dp(int c1, int c2, int c3, int c4, int pos) {
  if (pos >= n) return 0;
  int& ret = memo[c1][c2][c3][pos];
  if (~ret) return ret;
  ret = INT_MAX;
  if (c1 == 0) ret = min(ret, dp(c2, c3, c4, col[pos + 4], pos + 1));
  for (int r = 0; r < 4; r++) {
    if ((c1 >> r) & 1)
      ret = min(ret, a[1] + dp(c1 ^ (1 << r), c2, c3, c4, pos));
  }
  for (int r = 0; r < 3; r++) {
    int nc1 = c1, nc2 = c2;
    int ones = (1 << r) | (1 << (r + 1));
    nc1 = nc1 & (~ones);
    nc2 = nc2 & (~ones);
    ret = min(ret, a[2] + dp(nc1, nc2, c3, c4, pos));
  }
  for (int r = 0; r < 2; r++) {
    int nc1 = c1, nc2 = c2, nc3 = c3;
    int ones = (1 << r) | (1 << (r + 1)) | (1 << (r + 2));
    nc1 = nc1 & (~ones);
    nc2 = nc2 & (~ones);
    nc3 = nc3 & (~ones);
    ret = min(ret, a[3] + dp(nc1, nc2, nc3, c4, pos));
  }
  ret = min(ret, a[4] + dp(col[pos + 4], col[pos + 5], col[pos + 6],
                           col[pos + 7], pos + 4));
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int k = 1; k <= 4; k++) cin >> a[k];
  for (int r = 0; r < 4; r++) cin >> mat[r];
  for (int c = 0; c < n; c++) {
    int mask = 0;
    for (int r = 0; r < 4; r++)
      if (mat[r][c] == '*') mask |= (1 << r);
    col[c] = mask;
  }
  memset(memo, -1, sizeof memo);
  cout << dp(col[0], col[1], col[2], col[3], 0) << endl;
  return (0);
}
