题目描述

剧场的圆形舞台边缘依次摆放着 $n$ 盏信标灯，第 $i$ 盏灯写着一个小写字母 $s_i$，并记录了一个能量值 $a_i$。

现在要把这些信标灯两两连接。只有字母相同的两盏灯才能连接，连接第 $i$ 盏和第 $j$ 盏灯的花费为 $a_i\times a_j$。

所有连接线都会画在圆形舞台内部。为了避免线路冲突，任意两条连接线不能在圆内部相交，但允许在端点处相接。

请判断是否能够把所有信标灯全部配对；如果可以，输出最小总花费；如果不可以，输出 $-1$。

输入格式

第一行输入整数 $T$，表示测试组数。

每组数据第一行输入整数 $n$。

第二行输入长度为 $n$ 的字符串 $s$，其中 $s_i$ 表示第 $i$ 盏信标灯上的字母。

第三行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每盏信标灯的能量值。

输出格式

对每组数据输出一行一个整数。若可以完成所有配对，输出最小总花费；否则输出 $-1$。

样例

3
2
aa
5 7
4
abba
1 2 3 4
4
abab
1 10 2 20

35
10
-1

样例说明

第一组只能连接两盏 a 灯，花费为 $5\times7=35$。

第二组可以连接第 $1$ 盏和第 $4$ 盏、第 $2$ 盏和第 $3$ 盏，总花费为 $1\times4+2\times3=10$。

第三组若连接相同字母，则两条线段会相交，因此无解。

数据范围