小珅喜欢解决各种各样的问题。今天他发现了一个自己无法解决的问题，于是请求你的帮助。

小珅得到 $n$ 个只包含小写英文字母的字符串。他希望将这些字符串按字典序排列（即字典中的顺序），但他不能交换它们的位置。他唯一可以进行的操作是翻转任意一个字符串（即将第一个字符变为最后一个，第二个变为倒数第二个，依此类推）。

翻转第 $i$ 个字符串需要花费 $c_{i}$ 单位的能量。他想知道，为使字符串按照字典序排列，最少需要花费多少能量。

如果字符串 $A$ 是字符串 $B$ 的前缀且长度更短（即 $|A|<|B|$），则 $A$ 的字典序小于 $B$。如果两者互不为对方前缀，则在第一个不同的位置，$A$ 中的字符小于 $B$ 中的字符时，$A$ 的字典序小于 $B$。

对于本题目的判断，相邻的完全相同的字符串不会影响字典序排列的要求。

输入格式

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

第二行包含 $n$ 个整数 $c_{i}$（$0 \leq c_{i} \leq 10^{9}$），其中第 $i$ 个表示将第 $i$ 个字符串翻转所需消耗的能量。

接下来有 $n$ 行，每行一个仅由小写英文字母组成的字符串。所有字符串的总长度不超过 $100000$。

输出格式

如果无法通过翻转某些字符串使它们字典序排列，输出 $-1$。否则，输出小珅需要花费的最小总能量。

2
1 2
ba
ac

1

3
1 3 1
aa
ba
ac

1

2
5 5
bbb
aaa

-1

2
3 3
aaa
aa

-1

说明/提示

在第二个样例中，需要翻转第 $2$ 个或第 $3$ 个字符串，翻转第 $3$ 个字符串所需消耗的能量更小。

在第三个样例中，两个字符串翻转后保持不变，依然不是字典序排列，因此答案为 $-1$。

在第四个样例中，两个字符串均为仅含字母 'a' 的串，但按字典序，字符串 "aa" 应在字符串 "aaa" 前面，所以答案为 $-1$。