← 返回题目列表

Codeforces · 706/C

C. 难题

中文机器翻译题面 查看原题

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。