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.
import java.util.Arrays;
import java.util.Scanner;

public class f {
	public static void main(String[] Args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[4];
		for (int i = 0; i < 4; i++)
			a[i] = sc.nextInt();
		boolean[][] isDot = new boolean[4][n];
		for (int i = 0; i < 4; i++) {
			String s = sc.next();
			for (int j = 0; j < n; j++)
				isDot[i][j] = (s.charAt(j) == '.');
		}
		int oo = 987654321;
		int[] best = new int[(1 << 16)];
		int[] nxt = new int[(1 << 16)];
		Arrays.fill(best, oo);
		Arrays.fill(nxt, oo);
		int mask = 0;
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				if (!isDot[i][j])
					mask = (mask | (1 << (i + j * 4)));
		best[mask] = 0;

		for (int i = 0; i < n; i++) {
			Arrays.fill(nxt, oo);
			for (int j = (1 << 16) - 1; j >= 0; j--) {
				if (best[j] != oo) {
					if (best[j] < nxt[j]) {
						nxt[j] = best[j];
					}
					for (int aa = 0; aa < 4; aa++) {
						for (int ii = 0; ii + aa < 4; ii++) {
							int nMask = j;
							for (int iii = ii; iii <= aa + ii; iii++)
								for (int jjj = 0; jjj <= aa; jjj++) {
									nMask = nMask & (((1 << 16) - 1) ^ (1 << (iii + jjj * 4)));
								}
							if (best[nMask] > best[j] + a[aa]) {
								best[nMask] = best[j] + a[aa];
							}
							// print(j, nMask);
							// System.out.println(Integer.toBinaryString(j) + "
							// " + Integer.toBinaryString(nMask) + " "
							// + aa + " " + ii + " " + nxt[nMask]);
						}
					}
				}
			}
			for (int j = 0; j < (1 << 16); j++)
				nxt[j] = best[j];
			Arrays.fill(best, oo);
			mask = 0;
			if (i + 4 < n)
				for (int j = 0; j < 4; j++)
					if (!isDot[j][i + 4])
						mask = (mask | (1 << (12 + j)));
			// System.out.println(Integer.toBinaryString(mask));
			for (int j = 0; j < (1 << 16); j += 16) {
				best[(j >> 4) | mask] = nxt[j];
			}
		}
		System.out.println(best[0]);
	}

	public static void print(int m1, int m2) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if ((m1 & (1 << (i + j * 4))) != 0)
					System.out.print("*");
				else
					System.out.print(".");
			}
			System.out.print("  ");
			for (int j = 0; j < 4; j++) {
				if ((m2 & (1 << (i + j * 4))) != 0)
					System.out.print("*");
				else
					System.out.print(".");
			}
			System.out.println();
		}
	}
}
