题目大意

有 $N$ 个仅含小写字母的字符串 $S_1,S_2,\cdots,S_N$。你需要把从这些字符串中选择一些以任意顺序拼接起来，同一个字符串可以被选择多次。每选择一次 $S_i$，你都需要花费 $C_i$ 的代价，也就是说你选择 $S_i$ 所花费的代价为 $C_i$ 与 $S_i$ 被选择的次数之积。求使拼接得到的字符串为回文串所需的最小花费。若不管如何都无法拼接成回文串，输出 -1。

数据范围：$1 \le N \le 50$，$1 \le |S_i| \le 20$，$1 \le C_i \le 10^9$。

输入格式

第一行一个整数 $N$，接下来 $N$ 行每行一个字符串 $S_i$ 和一个整数 $C_i$。

输出格式

一个整数，为最小代价或 -1。

样例解释

样例 1：我们可以分别选择一次 abc 与 ba，拼接得到回文串 abcba，花费为 $(3+4=7)$，为最小值。

样例 2：选择一次 abcab，两次 cba，拼接得到回文串 abcabcbacba，花费为 $(5+3\times2=11)$，为最小值。

样例 3：选择 ab 与 cba 花费的代价比仅选择 a 更少。

样例 4：无法拼成回文串。

（翻译 by @CarroT1212）