困难的问题

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定 $n$ 个仅包含小写英文字母的字符串。你不能交换字符串的位置，但可以翻转任意字符串，即把字符顺序完全反转。翻转第 $i$ 个字符串需要花费 $c_i$ 单位能量。

求使整个字符串序列按字典序非递减排列所需的最小总能量。如果无法做到，输出 $-1$。

若字符串 $A$ 是字符串 $B$ 的真前缀，则 $A$ 的字典序更小；否则由第一个不同字符决定大小。相邻字符串完全相同是允许的。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，其中 $c_i$ 表示翻转第 $i$ 个字符串的代价。

接下来 $n$ 行，每行包含一个仅由小写英文字母组成的非空字符串。

输出格式

若无法使序列按字典序非递减排列，输出 $-1$；否则输出最小总能量。

样例输入 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\le n\le 100000$，$0\le c_i\le 10^9$，所有字符串的总长度不超过 $100000$。