瓦西里喜欢解决不同的任务。今天他发现了一个他自己无法解决的问题，所以他请求你的帮助。
瓦西里给出了n个由小写英文字母组成的字符串。他希望这些字符串按照字典顺序排序(就像在字典中那样)，但他不允许交换这些字符串中的任何一个。他允许做的唯一操作是将其中任何一个字符串反转(第一个字符变成最后一个字符，第二个字符变成最后一个字符之前的一个字符，以此类推)。
为了反转第i个字符串，瓦西里必须花费ci个单位的能量。他感兴趣的是，为了按字典顺序对字符串进行排序，他必须花费的最小能量。
如果字符串A比B短(|A|<|B|)并且是它的前缀，则字符串A在字典编法上比字符串B小；如果两个字符串A,B彼此都不是另一个字符串的前缀，并且从左到右第一个不相同的字符、A中的字符比B中的字符小，也称A比B小。
为了解决这个问题，且相邻的两个相等的字符串不能破坏序列按字典顺序排序的条件，求瓦西里必须花费的最小总能量。
输入的第一行包含一个整数n(2≤n≤100000)−字符串的个数。
第二行包含n个整数ci(0≤ci≤10^9)，第i个整数等于Vasiliy为了反转第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。
2
1 2
ba
ac1