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.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;


// graph, dfs,bfs, get connected components,iscycle, isbipartite, dfs on trees



public class scratch_25{
    static class Graph{

        public static class Vertex{
            HashMap<Integer,Long> nb= new HashMap<>();     // for neighbours of each vertex
        }

        public static HashMap<Integer,Vertex> vt;   // for vertices(all)

        public Graph(){
            vt= new HashMap<>();
        }

        public static int numVer(){
            return vt.size();
        }

        public static boolean contVer(int ver){
            return vt.containsKey(ver);
        }

        public static void addVer(int ver){
            Vertex v= new Vertex();
            vt.put(ver,v);
        }






        public static void addEdge(int ver1, int ver2, long weight){
            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }
            Vertex v1= vt.get(ver1);
            Vertex v2= vt.get(ver2);
            v1.nb.put(ver2,(long)weight);                                 // if previously there is an edge, then this replaces that edge
            v2.nb.put(ver1,(long)weight);
        }

        public static void delEdge(int ver1, int ver2){

            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }
            vt.get(ver1).nb.remove(ver2);
            vt.get(ver2).nb.remove(ver1);
        }
        public static void delVer(int ver){
            if(!vt.containsKey(ver)){
                return;
            }
            Vertex v1= vt.get(ver);
            ArrayList<Integer> arr= new ArrayList<>(v1.nb.keySet());
            for (int i = 0; i <arr.size() ; i++) {
                int s= arr.get(i);
                vt.get(s).nb.remove(ver);
            }
            vt.remove(ver);
        }
        static boolean done[];
        static int parent[];
        static ArrayList<Integer>vals= new ArrayList<>();


        public static boolean isCycle(int i){
            Stack<Integer>stk= new Stack<>();

            stk.push(i);
            while(!stk.isEmpty()){
                int x= stk.pop();
                vals.add(x);
                //   System.out.print("current="+x+" stackinit="+stk);
                if(!done[x]){
                    done[x]=true;
                }
                else if(done[x] ){
                    return true;
                }

                ArrayList<Integer>ar= new ArrayList<>(vt.get(x).nb.keySet());
                for (int j = 0; j <ar.size() ; j++) {
                    if(parent[x]!=ar.get(j)){
                        parent[ar.get(j)]=x;
                        stk.push(ar.get(j));
                    }
                }
                // System.out.println(" stackfin="+stk);
            }
            return false;
        }
        static int[]level;
        static int[] curr;
        static int[] fin;

        public static void dfs(int src){
            done[src]=true;
            level[src]=0;
            Queue<Integer>q= new LinkedList<>();
            q.add(src);
            while(!q.isEmpty()){
                int x= q.poll();
                ArrayList<Integer>arr= new ArrayList<>(vt.get(x).nb.keySet());
                for (int i = 0; i <arr.size() ; i++) {
                    int v= arr.get(i);
                    if(!done[v]){
                        level[v]=level[x]+1;
                        done[v]=true;
                        q.offer(v);
                    }
                }
            }
        }
        static int oc[];
        static int ec[];


        public static void dfs1(int src){
            Queue<Integer>q= new LinkedList<>();
            q.add(src);
            done[src]= true;
            //    int count=0;
            while(!q.isEmpty()){

                int x= q.poll();
                //   System.out.println("x="+x);
                int even= ec[x];
                int odd= oc[x];
                if(level[x]%2==0){
                    int val= (curr[x]+even)%2;
                    if(val!=fin[x]){
                        //  System.out.println("bc");
                        even++;
                        vals.add(x);
                    }
                }
                else{
                    int val= (curr[x]+odd)%2;
                    if(val!=fin[x]){
                        //   System.out.println("bc");
                        odd++;
                        vals.add(x);
                    }

                }
                ArrayList<Integer>arr= new ArrayList<>(vt.get(x).nb.keySet());
                //   System.out.println(arr);
                for (int i = 0; i <arr.size() ; i++) {
                    int v= arr.get(i);
                    if(!done[v]){
                        done[v]=true;
                        oc[v]=odd;
                        ec[v]=even;
                        q.add(v);
                    }
                }
            }

        }

        static long popu[];
        static long happy[];
        static long count[]; // total people crossing that pos
        static long sum[]; // total sum of happy people including that.


        HashMap<Integer, ArrayList<Integer>>map= new HashMap<>();
        public static void bfs(int x,ArrayList<Long>curr){



        }


        public static void bfs1(int x){
            done[x]=true;
//            long total= popu[x];
            long smile= 0;
            ArrayList<Integer>nbrs= new ArrayList<>(vt.get(x).nb.keySet());
            for (int i = 0; i <nbrs.size() ; i++) {
                int r= nbrs.get(i);
                if(!done[r]){
                    bfs1(r);
//                    total+=count[r];
                    smile+=happy[r];
                }
            }
//            count[x]=total;
            sum[x]=smile;
        }


    }




    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /**
         * call this method to initialize reader for InputStream
         */
        static void init(InputStream input) {
            reader = new BufferedReader(
                    new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /**
         * get next word
         */
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                //TODO add check for eof if necessary
                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());
        }
    }


    static class Pair implements Comparable<Pair>     {
        int val;
        int pos;


        public Pair(int val, int pos) {
            this.pos = pos;
            this.val = val;

        }
        @Override
        public String toString() {
            return val + " " + pos;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.pos >o.pos){
                return 1;
            }
            else if(this.pos==o.pos){

                return 0;
            }
            else{
                return -1;
            }
        }}



        static class Pair1 implements Comparable<Pair1>     {
            int val;
            int pos;


            public Pair1(int val, int pos) {
                this.pos = pos;
                this.val = val;

            }
            @Override
            public String toString() {
                return val + " " + pos;
            }

            @Override
            public int compareTo(Pair1 o) {
                if(this.val >o.val){
                    return 1;
                }
                else if(this.val==o.val){

                    return 0;
                }
                else{
                    return -1;
                }
            }
        }
    static ArrayList<Pair> findSubArrays(long[] arr, int n)
    {
        // create an empty map
        HashMap<Long,ArrayList<Integer>> map = new HashMap<>();

        // create an empty vector of pairs to store
        // subarray starting and ending index
        ArrayList<Pair> out = new ArrayList<>();

        // Maintains sum of elements so far
        long sum = 0;

        for (int i = 0; i < n; i++)
        {
            // add current element to sum
            sum += arr[i];

            // if sum is 0, we found a subarray starting
            // from index 0 and ending at index i
            if (sum == 0)
                out.add(new Pair(0, i));
            ArrayList<Integer> al = new ArrayList<>();

            // If sum already exists in the map there exists
            // at-least one subarray ending at index i with
            // 0 sum
            if (map.containsKey(sum))
            {
                // map[sum] stores starting index of all subarrays
                al = map.get(sum);
                for (int it = 0; it < al.size(); it++)
                {
                    out.add(new Pair(al.get(it) + 1, i));
                }
            }
            al.add(i);
            map.put(sum, al);
        }
        return out;
    }






    // After writing solution, quick scan for:
    //   array out of bounds
    //   special cases e.g. n=1?
    //
    // Big numbers arithmetic bugs:
    //   int overflow
    //   sorting, or taking max, or negative after MOD


    public static void main(String[] args)  throws IOException {
        Reader.init(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n= Reader.nextInt();
        long cost[]= new long[n];
        long dp[][]= new long[n][2];  //dp(i,j) will hopefully denote the minimum cost of first i strings, with j==1 if ith is reversed, and j==0 if not reversed.
        for (int i = 0; i <n ; i++) {
            cost[i]= Reader.nextLong();
            dp[i][0]= (long)1e16;
            dp[i][1]= (long)1e16;
        }
        String str[]= new String[n];
        for (int i = 0; i <n ; i++) {
            str[i]= Reader.next();
        }
        dp[0][0]=0;
        dp[0][1]=cost[0];
        for (int i = 1; i <n ; i++) {

            if(str[i-1].compareTo(str[i])<=0){
                dp[i][0]= Math.min(dp[i][0],dp[i-1][0]);    // previous is smaller than us
            }
            if(new StringBuilder(str[i-1]).reverse().toString().compareTo(str[i])<=0){
                dp[i][0]= Math.min(dp[i][0],dp[i-1][1]);                           // previous ka reverse is smaller than us
            }
            if(str[i-1].compareTo(new StringBuilder(str[i]).reverse().toString())<=0){
                dp[i][1]= Math.min(dp[i][1],dp[i-1][0]+cost[i]);                      // previous is smaller than us ka reverse
            }
            if(new StringBuilder(str[i-1]).reverse().toString().compareTo(new StringBuilder(str[i]).reverse().toString())<=0){
                dp[i][1]= Math.min(dp[i][1],dp[i-1][1]+cost[i]);                           // previous ka reverse is smaller than us ka reverse
            }


        }
        long min= Math.min(dp[n-1][0],dp[n-1][1]);
        if(min==(long)1e16){
            out.append(-1+"\n");
        }
        else{
            out.append(min+"\n");
        }







        out.flush();
        out.close();
        }

        public static boolean check(int arr[]){
        int sum=0;
        int n= arr.length;
            for (int i = 0; i <arr.length ; i++) {
                sum+=arr[i];
            }
            if(sum%2==1){
                return false;
            }

            else{
                sum/=2;
                boolean dp[][]= new boolean[n+1][sum+1]; // dp(i,j) will hopefully denote wheather making a sum of j is possible using the first i elements
                for (int i = 0; i <=n ; i++) {
                    dp[i][0]=true;
                }
                for (int i = 1; i <=n ; i++) {
                    for (int j = 0; j <=sum ; j++) {
                        if(arr[i-1]>j){
                            dp[i][j]=dp[i-1][j];
                        }
                        else{
                            dp[i][j]= dp[i-1][j] || dp[i-1][j-arr[i-1]];
                        }
                    }
                }
                return dp[n][sum];
            }

        }







    public static String convert(String s,int n){
        if(s.length()==n){
            return s;
        }
        else{
            int x= s.length();
            int v=n-x;
            String str="";
            StringBuilder s2= new StringBuilder();
            for (int i = 0; i <v ; i++) {
                s2.append('0');
            }
            StringBuilder s1= new StringBuilder(s);
            s2.append(s1);

//            str+=s;
            String q= s2.toString();
            return q;

        }
    }
    public static int lower(ArrayList<Integer>arr,int key){
        int low = 0;
        int high = arr.size()-1;
        while(low < high){
            int mid = low + (high - low)/2;
            if(arr.get(mid) >= key){
                high = mid;
            }
            else{
                low = mid+1;
            }
        }
        return low;
    }

    public static int upper(ArrayList<Integer>arr,int key){
        int low = 0;
        int high = arr.size()-1;
        while(low < high){
            int mid = low + (high - low+1)/2;
            if(arr.get(mid) <= key){
                low = mid;
            }
            else{
                high = mid-1;
            }
        }
        return low;
    }





    static long modExp(long a, long b, long mod) {
        //System.out.println("a is " + a + " and b is " + b);
        if (a==1) return 1;
        long ans = 1;
        while (b!=0) {
            if (b%2==1) {
                ans = (ans*a)%mod;
            }
            a = (a*a)%mod;
            b/=2;
        }
        return ans;
    }


    public static long modmul(long a, long b, long mod) {
        return b == 0 ? 0 : ((modmul(a, b >> 1, mod) << 1) % mod + a * (b & 1)) % mod;
    }

    static long sum(long n){
        //   System.out.println("lol="+ (n*(n-1))/2);
        return (n*(n+1))/2;
    }






    public static ArrayList<Integer> Sieve(int n) {
        boolean arr[]= new boolean [n+1];
        Arrays.fill(arr,true);
        arr[0]=false;
        arr[1]=false;
        for (int i = 2; i*i <=n ; i++) {
            if(arr[i]){
                for (int j = 2; j <=n/i ; j++) {
                    int u= i*j;
                    arr[u]=false;
                }}
        }
        ArrayList<Integer> ans= new ArrayList<>();
        for (int i = 0; i <n+1 ; i++) {
            if(arr[i]){
                ans.add(i);
            }
        }
        return ans;
    }




    static long power( long x, long y, long p)
    {

        long res = 1;


        x = x % p;

        if (x == 0) return 0;

        while (y > 0)
        {

            if((y & 1)==1)
                res = (res * x) % p;


            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static long ceil_div(long a, long b){
        return (a+b-1)/b;
    }

    static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a, b);
    }}

