题目描述

每个测试的时间限制：1 秒
每个测试的内存限制：256 兆字节

Vasiliy 喜欢解决各种难题。今天他发现了一道自己无法解决的问题，因此他请求你的帮助。

Vasiliy 有 $n$ 个由小写英文字母组成的字符串。他希望这些字符串按字典序排列（就像在字典中一样），但他不允许交换任何字符串。他唯一能做的操作是将任意字符串反转（第一个字符变为最后一个，第二个变为倒数第二个，依此类推）。

反转第 $i$ 个字符串需要花费 $c_i$ 单位的能量。他想知道，为了使得字符串按字典序排列，他需要花费的最小总能量。

字符串 $A$ 在字典序上小于字符串 $B$，如果：

• $A$ 是 $B$ 的前缀且 $|A| < |B|$，或者
• 在它们第一个不同的位置上，$A$ 的字符小于 $B$ 的字符。

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

输入格式

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

第二行包含 $n$ 个整数 $c_i$（$0 \le c_i \le 10^9$），其中第 $i$ 个整数表示反转第 $i$ 个字符串所需花费的能量。

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

输出格式

如果无法通过反转部分字符串使得它们按字典序排列，则输出 $-1$。否则，输出 Vasiliy 需要花费的最小总能量。

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$。