单点时限: 1.0 sec
内存限制: 512 MB
阿屈和室友蓬蓬最近在玩一种单词游戏，游戏规则如下：
- 开始时会给出 $N$ 个单词 $S_1, S_2, …, S_N$
- 每个玩家选择至少一个单词（可以重复选则某个单词 $S_i$），拼接形成回文串
- 率先得到回文串的玩家获胜
蓬蓬发现他每次都打不过阿屈，于是他修改了游戏规则：
- 每个单词 $S_i$ 赋予一个值 $1\le C_i \le 10^9$，每选择一次 $S_i$ 就要付出 $C_i$ 的代价
- 构成回文串且所用代价最小的玩家获胜
阿屈虽然能很快得到回文串，但却不擅长得到最小代价回文串，这撼动了他在单词游戏中的统治地位。你能帮助阿屈计算出构成回文串的最小代价吗？
第一行一个正整数 $N$ ($1\le N \le 100$)。
接下来 $N$ 行，每行一个字符串 $S_i$ ($1\le |S_i| \le 60$) 以及一个正整数 $C_i$ ($1\le C_i \le 10^9$) 表示选择该字符串的代价。
输出一个正整数 cost，表示阿屈用所给单词 $S_1, S_2, …, S_N$ 构成回文串的最小代价。若无法构成回文串，输出 -1。
4 ab 5 cba 3 a 12 ab 10
8
2 abc 1 ab 2
-1
2 abcab 5 cba 3
11
$1\le N\le100$
$1\le|S_i|\le 60$
$1\le C_i \le 10^9$
$S_i$ 只包含小写字母
在样例 1 中，可以选择 a 直接构成回文串，所需代价为 12，但选择 ab 和 cba 构成回文串 abcba 的代价为 8。
在样例 2 中，无法构成回文串，输出 -1。
在样例 3 中，选择 abcab 一次、cba 两次，构成回文串 abcab|cba|cba，最小代价为 11。