Vasiliy 喜欢解决不同的任务。今天他发现一个他自己无法解决的问题,所以他请求你帮忙。
Vasiliy 被赋予 n 个由小写英文字母组成的字符串。他希望它们按字典顺序(如字典中的顺序)排序,但不允许交换其中任何一个。他唯一可以做的操作就是反转其中的任何一个(第一个字符变成最后一个,第二个变成最后一个之前的字符,依此类推)。
为了反转第 i 个字符串,瓦西里必须花费 ci 单位的能量。他感兴趣的是为了让字符串按字典顺序排序而必须花费最少的精力。
如果字符串 A 比 B 短 (|A| < |B|) 并且是字符串 B 的前缀,或者如果它们都不是另一个的前缀,并且在它们不同的第一个位置,A 中的字符小于 B 中的字符,则字符串 A 按字典顺序小于字符串 B。
就本问题而言,相邻的两个相等的字符串不会破坏序列按字典顺序排序的条件。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 100 000) — 字符串的数量。
第二行包含 n 个整数 ci (0 ≤ ci ≤ 109),其中第 i 个整数等于 Vasiliy 反转第 i 个字符串所需消耗的能量。
接下来n行,每行包含一个由小写英文字母组成的字符串。这些字符串的总长度不超过 100 000。
输出
如果无法反转某些字符串以使它们按字典顺序定位,则打印 - 1。否则,打印 Vasiliy 必须花费的最小总能量。
示例
输入 #1
2 1 2 ba ac
输出 #1
1
输入 #2
3 1 3 1 aa ba ac
输出 #2
1
输入 #3
2 5 5 bbb aaa
输出 #3
-1
输入#4
2 3 3 aaa aa
输出#4
-1
注意
在第二个样本中,必须反转弦 2 或弦 3。反转弦 3 所需的能量较小。
在第三个示例中,两个字符串在反转后都没有改变,而且它们的顺序错误,所以答案是 - 1。
在第四个示例中,两个字符串均仅包含字符“a”,但按照排序顺序,字符串“aa”应位于字符串“aaa”之前,因此答案为 - 1。