题目描述

有 $n$ 个字符串 $s_1, s_2, \ldots, s_n$。

你可以翻转每个字符串，翻转一次第 $i$ 个字符串的费用是 $c_i$。

你需要使用最少的费用使得这些字符串是按照字典序升序的顺序排列的。即：你需要保证最终字符串 $s_1$ 的字典序是小于等于字符串 $s_2$ 的，同时字符串 $s_2$ 的字典序是小于等于字符串 $s_3$ 的，……，同时字符串 $s_{n-1}$ 的字典序是小于等于字符串 $s_n$ 的。

注意：你不能调整这 $n$ 个字符串之间的顺序，你只能对每个字符串进行翻转。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

第二行，$n$ 个整数 $c_1, c_2, \ldots, c_n(0 \le c_i \le 10^9)$，表示翻转每个字符串的费用。

接下来 $n$ 行，每行包含一个字符串，依次表示字符串 $s_1, s_2, \ldots, s_n$。

输出格式

如果无论怎么翻转都无法保证这些字符串按照字典序升序排列，输出 $-1$。

否则，输出一个整数，表示将这 $n$ 个字符串按字典序升序排列所需的最少总费用。

3
1 3 1
aa
ba
ac

1

5
1 2 3 4 5
ca
cb
bc
ca
cc

3

2
5 5
abc
aa

-1

说明/提示

样例解释

样例1：

最优方案是花费 $1$ 翻转 $s_3$，则：

• $s_1 = \mathtt{aa}$
• $s_2 = \mathtt{ba}$
• $s_2 = \mathtt{ca}$

按字典序升序排列，总费用为 $1$。

样例2：

最优方案是花费 $1$ 翻转 $s_1$，再花费 $2$ 翻转 $s_2$，则：

• $s_1 = \mathtt{ac}$
• $s_2 = \mathtt{bc}$
• $s_3 = \mathtt{bc}$
• $s_4 = \mathtt{ca}$
• $s_5 = \mathtt{cc}$

按字典序升序排列，总费用为 $1 + 2 = 3$。

（题目描述中有说明，本题中按字典序升序排列只要求排在前面的字符串的字典序小于等于排在后面的字符串的字典序即可）

样例3：

不存在合法的翻转方案。因为字符串 $\mathtt{abc}$ 不论翻转（$\mathtt{cba}$）还是不翻转（$\mathtt{abc}$），它的字典序都比 $\mathtt{aa}$ 大。

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10, c_i \le 100$
• 对于 $50\%$ 的数据，$n \le 1000, c_i \le 10^6$；
• 对于 $100\%$ 的数据，$2 \le n \le 10^5, 0 \le c_i \le 10^9$；每个字符串 $s_i$ 均由小写英文字母组成，且长度不超过 $10$。