CF706C.Hard problem

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 c__i 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.

瓦西里喜欢解决各种题目。今天他遇到了一道自己无法解决的题目，因此他请你帮忙。

瓦西里得到了 $n$ 个由小写英文字母组成的字符串。他希望将这些字符串按字典序（即字典中的顺序）排列，但他不允许交换任意两个字符串的位置。他唯一被允许的操作是：对任意一个字符串进行反转（即第一个字符变为最后一个，第二个字符变为倒数第二个，依此类推）。

对第 $i$ 个字符串执行反转操作需要消耗 $c_i$ 单位的能量。他想知道：为使所有字符串按字典序排列，所需的最小能量总和是多少？

字符串 $A$ 在字典序上小于字符串 $B$，当且仅当以下任一条件成立：

• $A$ 是 $B$ 的前缀且长度更短（即 $|A| < |B|$），或
• $A$ 与 $B$ 彼此均非对方的前缀，且在二者首次出现不同字符的位置上，$A$ 中该位置的字符字典序小于 $B$ 中对应位置的字符。

在本题中，相邻两个相等的字符串不会破坏序列的字典序排序条件。

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 c__i (0 ≤ c__i ≤ 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.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）—— 字符串的个数。

第二行包含 $n$ 个整数 $c_i$（$0 \leq c_i \leq 10^9$），其中第 $i$ 个数表示瓦西里反转第 $i$ 个字符串所需消耗的能量。

接下来是 $n$ 行，每行包含一个仅由小写英文字母组成的字符串。这些字符串的总长度不超过 $100\,000$。

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.

如果无法通过翻转其中一些字符串使得它们按字典序排列，则输出 -1。否则，输出瓦西里需要消耗的最小总能量。

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.

在第二个样例中，需要反转字符串 2 或字符串 3。其中反转字符串 3 所需的能量更少。

在第三个样例中，两个字符串反转后均不发生变化，但它们的顺序仍是错误的，因此答案为 $-1$。

在第四个样例中，两个字符串均由字符 'a' 组成，但在字典序中字符串 "aa" 应排在字符串 "aaa" 之前，因此答案为 $-1$。