Vasiliy is fond of solving different tasks. Today he found one he wasn't able to solve himself, so he asks you to help.

Vasiliy is given n strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).

To reverse the i-th string Vasiliy has to spent ci units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.

String A is lexicographically smaller than string B if it is shorter than B (|A| < |B|) and is its prefix, or if none of them is a prefix of the other and at the first position where they differ character in A is smaller than the character in B.

For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of strings.

The second line contains n integers ci (0 ≤ ci ≤ 109), the i-th of them is equal to the amount of energy Vasiliy has to spent in order to reverse the i-th string. 

Then follow n lines, each containing a string consisting of lowercase English letters. The total length of these strings doesn't exceed 100 000.

Output

If it is impossible to reverse some of the strings such that they will be located in lexicographical order, print  - 1. Otherwise, print the minimum total amount of energy Vasiliy has to spent.

Examples

Input

2
1 2
ba
ac


Output

1


Input

3
1 3 1
aa
ba
ac


Output

1


Input

2
5 5
bbb
aaa


Output

-1


Input

2
3 3
aaa
aa


Output

-1

Note

In the second sample one has to reverse string 2 or string 3. To amount of energy required to reverse the string 3 is smaller.

In the third sample, both strings do not change after reverse and they go in the wrong order, so the answer is  - 1.

In the fourth sample, both strings consists of characters 'a' only, but in the sorted order string "aa" should go before string "aaa", thus the answer is  - 1.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.security.interfaces.DSAKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class a {

	public static class in {
		static BufferedReader reader;
		static StringTokenizer tokenizer;

		static void init(InputStream input) throws FileNotFoundException {
			// reader = new BufferedReader(new
			// FileReader("B-small-attempt4.in"));
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}

		static String next() throws IOException {
			while (!tokenizer.hasMoreTokens())
				tokenizer = new StringTokenizer(reader.readLine());
			return tokenizer.nextToken();
		}

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

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

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

	public static long comp(int n, int r) {
		r = Math.min(r, n - r);
		long ans = 1;
		for (int i = 1; i <= r; i++) {
			ans = ans * (long) (n - r + i) / (long) i;
		}
		return ans;

	}

	public static class node {

		int st;
		int end;
		int p;

		node(int st, int end, int p) {
			this.st = st;
			this.end = end;
			this.p = p;

		}

	}

	public static int gcd(int x, int y) {
		if (y == 0)
			return x;
		return gcd(y, x % y);
	}

	public static int tree[];

	public static void add(int idx, long val, int n, int tree[]) {

		while (idx <= n) {
			tree[idx] += val;
			idx += (idx & -idx);
		}
	}

	public static int get(int idx) {
		int g = 0;
		while (idx > 0) {

			g += tree[idx];
			idx -= (idx & -idx);
		}

		return g;
	}

	public static class point implements Comparable<point> {
		int min;
		int a;
		int b;

		point(int min, int a, int b) {
			this.min = min;
			this.a = a;
			this.b = b;
		}

		@Override
		public int compareTo(point o) {
			if (o.min > min)
				return 1;
			else if (o.min < min)
				return -1;
			return 0;
		}
	}

	// for bad input
	static String ReadLn(int maxLg) {
		byte lin[] = new byte[maxLg];
		int lg = 0, car = -1;
		String line = "";

		try {
			while (lg < maxLg) {
				car = System.in.read();
				if ((car < 0) || (car == '\n'))
					break;
				lin[lg++] += car;
			}
		} catch (IOException e) {
			return (null);
		}

		if ((car < 0) && (lg == 0))
			return (null);
		return (new String(lin, 0, lg));
	}

	// IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
	// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
	// DEFINE ANY CLASS AND METHOD NEEDED
	// LNode CLASS IS DEFINED BY DEFAULT
	// CLASS BEGINS, THIS CLASS IS REQUIRED

	public class LNode {
		public int value;
		public LNode next;

	}

	public static class ReverseLinkedList {
		// METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
		public static LNode reverseLinkedList(LNode list) {
			// INSERT YOUR CODE HERE
			int n = 0;
			LNode pointer = list;
			while (pointer != null) {
				n++;
				pointer = pointer.next;
			}

			int mid = (n + 1) / 2;
			if (n % 2 == 1)
				mid--;
			LNode arr[] = new LNode[n - mid];
			pointer = list;
			int p = 0;
			int c = 0;
			while (pointer != null) {

				if (c >= mid) {
					arr[p++] = pointer;
				}
				c++;
				pointer = pointer.next;
			}
			LNode swap = null;
			for (int i = 0; i < (n - mid) / 2; i++) {
				swap = arr[i];
				arr[i] = arr[n - mid - 1 - i];
				arr[n - mid - 1 - i] = swap;
			}

			pointer = list;
			p = 0;
			c = 0;
			while (pointer != null) {

				if (c >= mid - 1) {
					pointer.next = arr[p++];
				}
				c++;
				pointer = pointer.next;
			}

			return list;
		}
		// METHOD SIGNATURE ENDS
	}

	public static class points implements Comparable<points> {

		int dur;
		int idx;

		points(int d, int i) {
			dur = d;
			idx = i;
		}

		@Override
		public int compareTo(points o) {
			if (o.dur < dur)
				return 1;
			else if (o.dur > dur)
				return -1;
			else if (o.idx < idx)
				return 1;
			else
				return -1;

		}
	}

	public static String rev(String a) {
		char b[] = a.toCharArray();

		for (int i = 0; i < b.length / 2; i++) {
			char temp = b[i];
			b[i] = b[b.length - 1 - i];
			b[b.length - 1 - i] = temp;
		}
		String ans = "";
		for (int i = 0; i < b.length; i++) {
			ans += b[i];
		}
		return ans;
	}

	public static long dp[][];
	public static int n;
	public static String arr[];
	public static boolean tt = false;
	public static int a[];
	public static String r[];

	public static long solve(int i, int rev) {
		if (i >= n)
			return 0;

		if (dp[i][rev] != -1)
			return dp[i][rev];
		long min = Long.MAX_VALUE;
		if (rev == 0) {
			boolean ok = true;
			if (arr[i].compareTo(arr[i - 1]) >= 0) {
				min = Math.min(min, solve(i + 1, 0));
				ok = false;
			}
			if (r[i].compareTo(arr[i - 1]) >= 0) {
				min = Math.min(min, solve(i + 1, 1) + (long) a[i]);
				ok = false;
			}
			if (ok)
				return 1L << 60;

		} else {
			boolean ok = true;
			if (arr[i].compareTo(r[i - 1]) >= 0) {
				min = Math.min(min, solve(i + 1, 0));
				ok = false;

			}
			if (r[i].compareTo(r[i - 1]) >= 0) {
				min = Math.min(min, solve(i + 1, 1) + (long) a[i]);
				ok = false;
			}
			if (ok)
				return 1L << 60;
		}

		return dp[i][rev] = min;

	}

	public static void main(String[] args) throws IOException {
		// StringBuilder qq = new StringBuilder();
		in.init(System.in);
		PrintWriter out = new PrintWriter(System.out);
		BufferedReader inp = new BufferedReader(
				new InputStreamReader(System.in));
	//	System.out.println(1L<<60); 
		n = in.nextInt();
		a = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = in.nextInt();
		}
		arr = new String[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = in.next();
		}
		r = new String[n];
		for (int i = 0; i < arr.length; i++) {
			r[i] = rev(arr[i]);
		}
		dp = new long[n][2];
		for (int i = 0; i < n; i++) {
			Arrays.fill(dp[i], -1);
		}
		long ans = Math.min(solve(1, 0), solve(1, 1) + (long) a[0]);
		out.println(ans >= 1L << 60 ? -1 : ans);
		out.close();

	}
}
