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.
## 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 _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.
## 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.
[samples]
## 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.
Vasiliy 喜欢解决各种问题。今天他遇到了一个自己无法解决的问题，因此他请求你的帮助。
Vasiliy 被给予 #cf_span[n] 个由小写英文字母组成的字符串。他希望将这些字符串按字典序（如字典中所示）排序，但他不允许交换其中任意两个字符串。他唯一允许的操作是反转其中任意一个字符串（第一个字符变为最后一个，第二个变为倒数第二个，依此类推）。
为了反转第 #cf_span[i] 个字符串，Vasiliy 需要花费 #cf_span[ci] 单位的能量。他希望找到最小的能量消耗，使得所有字符串按字典序排列。
字符串 #cf_span[A] 字典序小于字符串 #cf_span[B]，当且仅当：#cf_span[A] 比 #cf_span[B] 短（#cf_span[|A| < |B|]）且是 #cf_span[B] 的前缀，或者两者互不为前缀，且在第一个不同的位置上，#cf_span[A] 的字符小于 #cf_span[B] 的字符。
在本题中，两个相等的字符串相邻并不破坏序列字典序有序的条件。
输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）— 字符串的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[ci]（#cf_span[0 ≤ ci ≤ 10^9]），第 #cf_span[i] 个整数表示反转第 #cf_span[i] 个字符串所需消耗的能量。
接下来是 #cf_span[n] 行，每行包含一个由小写英文字母组成的字符串。这些字符串的总长度不超过 #cf_span[100 000]。
如果无法通过反转某些字符串使其按字典序排列，请输出 #cf_span[ - 1]。否则，请输出 Vasiliy 所需消耗的最小总能量。
在第二个样例中，必须反转第 #cf_span[2] 个字符串或第 #cf_span[3] 个字符串。反转第 #cf_span[3] 个字符串所需能量更小。
在第三个样例中，两个字符串反转后均不变，且顺序错误，因此答案为 #cf_span[ - 1]。
在第四个样例中，两个字符串都仅由字符 '_a_' 组成，但在字典序中字符串 "_aa_" 应排在 "_aaa_" 前面，因此答案为 #cf_span[ - 1]。
## Input
输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）— 字符串的数量。第二行包含 #cf_span[n] 个整数 #cf_span[ci]（#cf_span[0 ≤ ci ≤ 10^9]），第 #cf_span[i] 个整数表示反转第 #cf_span[i] 个字符串所需消耗的能量。接下来是 #cf_span[n] 行，每行包含一个由小写英文字母组成的字符串。这些字符串的总长度不超过 #cf_span[100 000]。
## Output
如果无法通过反转某些字符串使其按字典序排列，请输出 #cf_span[ - 1]。否则，请输出 Vasiliy 所需消耗的最小总能量。
[samples]
## Note
在第二个样例中，必须反转第 #cf_span[2] 个字符串或第 #cf_span[3] 个字符串。反转第 #cf_span[3] 个字符串所需能量更小。
在第三个样例中，两个字符串反转后均不变，且顺序错误，因此答案为 #cf_span[ - 1]。
在第四个样例中，两个字符串都仅由字符 '_a_' 组成，但在字典序中字符串 "_aa_" 应排在 "_aaa_" 前面，因此答案为 #cf_span[ - 1]。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of strings.
Let $ c = (c_1, c_2, \dots, c_n) \in \mathbb{Z}_{\geq 0}^n $ be the energy cost vector, where $ c_i $ is the cost to reverse the $ i $-th string.
Let $ S = (s_1, s_2, \dots, s_n) $ be the sequence of strings, where each $ s_i $ is a string over the lowercase English alphabet.
Let $ s_i^R $ denote the reverse of string $ s_i $.
For each string $ s_i $, define two possible states:
- **State 0**: string remains as $ s_i $, with cost $ 0 $.
- **State 1**: string is reversed to $ s_i^R $, with cost $ c_i $.
Let $ x_i \in \{0, 1\} $ indicate the choice for string $ i $:
- $ x_i = 0 $: use $ s_i $,
- $ x_i = 1 $: use $ s_i^R $.
**Constraints**
1. $ 2 \leq n \leq 100{,}000 $
2. $ 0 \leq c_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
3. Total length of all strings $ \leq 100{,}000 $
4. The sequence $ (t_1, t_2, \dots, t_n) $, where $ t_i = \begin{cases} s_i & \text{if } x_i = 0 \\ s_i^R & \text{if } x_i = 1 \end{cases} $, must satisfy:
$$
t_i \leq_{\text{lex}} t_{i+1} \quad \text{for all } i \in \{1, \dots, n-1\}
$$
where $ \leq_{\text{lex}} $ denotes lexicographical order (as defined: prefix relation or first differing character).
**Objective**
Minimize the total energy cost:
$$
\sum_{i=1}^n x_i \cdot c_i
$$
subject to the lexicographical ordering constraint. If no valid sequence $ (x_1, \dots, x_n) $ exists, output $ -1 $.