Bingbong 给定一个长度为 且仅包含小写字母的字符串 ，同时给定一个长度为 的数组 （注意下标从 开始）。 现将此字符串中的字母按照顺时针依次放置在圆上的不同位置，你需要每次选中两个索引 ，在其两个字符所在的点上连接一条线段，忽略所有点和线的粗细，且每个点恰好被一条线段连接，连接代价为 。 你需要计算所有合法的连线方式中，线段之间不相交的最少代价。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入一个整数 ，表示字符串的长度。第二行输入一个仅由小写字母组成的，长度为 的字符串 。第三行输入 个整数 ，表示每个字母的连接代价。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

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