CF706C Hard problem

Vasiliy 喜欢解决各种各样的问题。今天他发现了一个自己无法解决的问题，于是请求你的帮助。 Vasiliy 得到 $ n $ 个只包含小写英文字母的字符串。他希望将这些字符串按字典序排列（即字典中的顺序），但他不能交换它们的位置。他唯一可以进行的操作是翻转任意一个字符串（即将第一个字符变为最后一个，第二个变为倒数第二个，依此类推）。 翻转第 $ i $ 个字符串需要花费 $ c_{i} $ 单位的能量。他想知道，为使字符串按照字典序排列，最少需要花费多少能量。 如果字符串 $ A $ 是字符串 $ B $ 的前缀且长度更短（即 $ |A|

输入的第一行包含一个整数 $ n $（$ 2 \leq n \leq 100000 $）——字符串的数量。 第二行包含 $ n $ 个整数 $ c_{i} $（$ 0 \leq c_{i} \leq 10^{9} $），其中第 $ i $ 个表示将第 $ i $ 个字符串翻转所需消耗的能量。 接下来有 $ n $ 行，每行一个仅由小写英文字母组成的字符串。所有字符串的总长度不超过 $ 100000 $。

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

在第二个样例中，需要翻转第 $ 2 $ 个或第 $ 3 $ 个字符串，翻转第 $ 3 $ 个字符串所需消耗的能量更小。 在第三个样例中，两个字符串翻转后保持不变，依然不是字典序排列，因此答案为 $ -1 $。 在第四个样例中，两个字符串均为仅含字母 'a' 的串，但按字典序，字符串 "aa" 应在字符串 "aaa" 前面，所以答案为 $ -1 $。 由 ChatGPT 5 翻译