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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class f3 {
	static int n, prices[] = new int[4];
	static boolean world[][];

	public static class state {
		int h[];
		int enc;
		state(int A, int B, int C, int D) {
			h = new int[4];
			h[0] = A;h[1] = B;h[2] = C;h[3] = D;
			enc = h[0]+5*h[1]+25*h[2]+125*h[3];
		}
		
		void decrement() {
			for(int i = 0; i < 4; i++)
				h[i]--;
		}
		
		void posInc(boolean newH[]) {
			for(int i = 0; i < 4; i++) {
				if(h[i] < 3) continue;
				if(newH[i]) h[i]++;
			}
		}
		
		state apply(int col, int mag) {
			state s = new state(h[0],h[1],h[2],h[3]);
			for(int i = col; i < col + mag + 1; i++) {
				s.h[i] = Math.max(h[i], mag+1);
			}
			return s;
		}
		
		@Override
		public String toString() {
			return "[" +h[0] +","+h[1] +","+h[2] +","+h[3] +"]";
		}
		
		void reEncode() {
			enc = h[0]+5*h[1]+25*h[2]+125*h[3];
		}
	}
	
	static int memo[][][];
	
	static int go(int row, int col,int a, int b, int c, int d) {
		state heights = new state(a,b,c,d);
		if(col == 4) {
			heights.decrement();
			int h[] = new int[4];
			for(int i = 0; i < 4 ; i++) {
				for(int j = 0; j < 5; j++) {
					if(j == 4) h[i] = 4;
					if(j + row +1>= n) {
						h[i] = 4;
						break;
					}
					if(!world[row+1+j][i] && j >= heights.h[i]) {
						h[i] = j;
						break;
					}
				}
			}
			heights.h = h;
			heights.reEncode();
			
			return go(row+1, 0, heights.h[0],heights.h[1],heights.h[2],heights.h[3]);
		}
		
		if(row == n) return 0;
		if(memo[row][col][heights.enc] != -1) 
			return memo[row][col][heights.enc];
		int ans = Integer.MAX_VALUE/2;

		
		if (heights.h[col] > 0) {
			ans = go(row, col + 1, heights.h[0], heights.h[1], heights.h[2], heights.h[3]);
		}
		for(int i = 0; i < 4; i++) {
			if(row + i < n && col + i < 4) {
				state ns = heights.apply(col, i);
				ns.reEncode();
				ans = Math.min(ans,go(row, col+1, ns.h[0],ns.h[1],ns.h[2],ns.h[3]) + prices[i]);
			}
		}
		return memo[row][col][heights.enc] = ans;
	}
	
	public static void main(String args[]) throws IOException {
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		//BEGIN HERE
		n = in.nextInt();
		for(int i = 0; i < 4; i++) 
			prices[i] = in.nextInt();
		
		world = new boolean[n][4];
		for(int i = 0; i < 4; i++) {
			String s = in.next();
			for(int j = 0; j < n;j++) {
				world[j][i] = s.charAt(j) == '.';
			}
		}
		
		memo = new int[n][4][630];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 4; j++) {
				Arrays.fill(memo[i][j], -1);
			}
		}
		int h[] = new int[4];
		for(int i = 0; i < 4; i++) {
			for(int j = 0; j < 5; j++) {
				if(j == 4 || !world[j][i]) {
					h[i] = j;
					break;
				}
			}
		}
		state s = new state(h[0],h[1],h[2],h[3]);
		System.out.println(go(0,0,h[0],h[1],h[2],h[3]));
		out.close();
	}

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(InputStream i) {
			br = new BufferedReader(new InputStreamReader(i));
			st = null;
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			if (st == null) {
				st = new StringTokenizer(br.readLine());
			}
			String line = st.nextToken("\n");
			st = null;
			return line;
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	}

	public static class combinatorics {
		static long modInv(long a, long b) {
			return 1 < a ? b - modInv(b % a, a) * b / a : 1;
		}

		static long factorial[], mod;

		combinatorics(int n, long MOD) {
			mod = MOD;
			factorial = new long[n + 1];
			factorial[0] = 1;
			for (int i = 1; i <= n; i++) {
				factorial[i] = i * factorial[i - 1];
				factorial[i] %= mod;
			}
		}

		static long nCr(int n, int r) {
			if (r > n)
				return 0;
			return (factorial[n] * modInv((factorial[n - r] * factorial[r]) % mod, mod)) % mod;
		}
	}

}
