单词接龙（word）

【题目描述】

有 $n$ 个由小写英文字母组成的单词，第 $i$ 个单词为 $s_i$。选择单词 $i$ 需要消耗 $c_i$ 点脑力。

酒狐要选择若干个单词组成接龙序列。序列必须满足：

1. 第一个单词必须是单词 $1$，最后一个单词必须是单词 $n$；
2. 每个单词最多选择一次；
3. 对于相邻的两个单词，前一个单词的最后一个字符必须等于后一个单词的第一个字符。

接龙的脑力消耗等于所有被选单词的脑力消耗之和，单词 $1$ 和单词 $n$ 的费用也要计算。请求出合法接龙的最小脑力消耗。如果无法从单词 $1$ 接到单词 $n$，输出 -1。

【输入格式】

输入的第一行包含一个正整数 $T$，表示测试数据组数。

接下来依次输入 $T$ 组数据。每组数据的第一行包含一个正整数 $n$。

接下来 $n$ 行，每行包含一个字符串 $s_i$ 和一个正整数 $c_i$，分别表示第 $i$ 个单词和选择它所需的脑力消耗。

【输出格式】

对于每组数据输出一行一个整数，表示最小脑力消耗；如果不存在合法接龙，输出 -1。

【样例1输入】

2
5
ab 4
bc 2
bd 10
cd 3
de 1
3
ab 2
cd 3
ef 4

【样例1输出】

10
-1

【样例1解释】

第一组数据可以选择单词 $1,2,4,5$，得到 ab -> bc -> cd -> de，总脑力消耗为 $4+2+3+1=10$。

第二组数据中，单词 ab 无法接到单词 ef。

【数据范围】

对于 $30\%$ 的数据，$n\le 8$。

对于 $50\%$ 的数据，$n\le 18$。

对于编号为奇数的测试点，所有 $c_i=1$。

对于 $100\%$ 的数据，$1\le T\le 100$，$2\le n\le 300$，$1\le |s_i|\le 10$，$1\le c_i\le 10^9$，且单个测试点中所有 $n$ 的总和不超过 $3000$。