竹摇清风拂面

题号：NC310934
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Bingbong 给定一个长度为 $n$ 且仅包含小写字母的字符串 $s_0s_1\cdots s_{n-1}$ ，同时给定一个长度为 $n$ 的数组 $a_0,a_1,\dots,a_{n-1}$ （注意下标从 $0$ 开始）。
$\hspace{15pt}$ 现将此字符串中的字母按照顺时针依次放置在圆上的不同位置，你需要每次选中两个索引 $i,j\left(i\neq j;\,s_i=s_j\right)$ ，在其两个字符所在的点上连接一条线段，忽略所有点和线的粗细，且每个点恰好被一条线段连接，连接代价为 $a_i\times a_j$ 。
$\hspace{15pt}$ 你需要计算所有合法的连线方式中，线段之间不相交的最少代价。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示字符串的长度。
第二行输入一个仅由小写字母组成的，长度为  的字符串 。
第三行输入  个整数 ，表示每个字母的连接代价。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。如果不存在合法的连线方式，则输出 ；否则输出一个整数，表示所有合法的连线方式中，线段之间不相交的最少代价。

示例1

输入

复制

3
4
aabb
1 2 3 4
4
abab
1 2 3 4
4
aaaa
1 2 3 4

输出

复制

14
-1
10

说明

对于第一组测试数据，有且仅有一种连接方式，且线段不相交（见下图左），答案即为 。


对于第二组测试数据，有且仅有一种连接方式，且线段相交（见上图右），因此输出 。