考虑一个由英文小写和大写字母组成的字符集。我们对字符集中的字母进行编号，使得小写字母的编号为 $1$ 到 $26$（按字母顺序），大写字母的编号为 $27$ 到 $52$（同样按字母顺序）。例如，字符 b 的编号为 $2$，字符 Y 的编号为 $51$。

给你一个字符串 $s$，它由字符集的前 $k$ 个字符组成。同时给你一个大小为 $k \times k$ 的非负整数矩阵 $C$。元素 $C_{i,j}$ 表示在字符串 $s$ 的某个位置将编号为 $i$ 的字符修改为编号为 $j$ 的字符的代价。保证 $C_{i,i} = 0$。

你需要修改字符串 $s$ 中的某些字符，使得 $s$ 不包含任何长度大于 $1$ 的回文子串。同时，求出达到这一目标的最小总代价。

注意，在不同位置将编号为 $i$ 的字符修改为编号为 $j$ 的字符的代价是分别计算的。还需注意，每个位置的字符最多只能修改一次。

输入格式

第一行包含一个整数 $k$（$1 \le k \le 52$）—— 字符集的大小。

第二行包含一个字符串 $s$（$1 \le |s| \le 5 \cdot 10^6$），仅由编号不大于 $k$ 的英文小写和大写字母组成。

接下来的 $k$ 行中，第 $i$ 行包含 $k$ 个整数 $C_{i,j}$（$0 \le C_{i,j} \le 10^9$）—— 将编号为 $i$ 的字符修改为编号为 $j$ 的字符的代价。

注意，字符串 $s$ 的长度可能非常大，因此请使用快速的输入方法（例如 C++ 中的 scanf 函数或 Java 中的 BufferedReader 类）。

输出格式

如果可以得到一个不包含长度大于 $1$ 的回文子串的字符串，输出一个整数 $c$ —— 获得该字符串的最小代价。否则，输出唯一的整数 -1。

样例

输入 1

3
aaa
0 7 5
1 0 1
1 1 0

输出 1

12

输入 2

3
abc
0 1 1
1 0 1
1 1 0

输出 2

0