AT_abc175_f [ABC175F] Making Palindrome

给定 $N$ 个由小写英文字母组成的字符串 $S_1,S_2,\ldots,S_N$。 高桥想从这些字符串中选择至少一个字符串（允许重复选择），并将选出的字符串按照任意顺序拼接，使得到的字符串是一个回文串。 每使用一次字符串 $S_i$，需要花费 $C_i$ 的代价。如果多次使用同一个字符串，则每次使用都需要支付相应的代价。 求构造回文串所需的最小总代价。如果无法构造出回文串，输出 $-1$。

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

输出一个整数，表示构造回文串所需的最小总代价。如果无法构造出回文串，输出 $-1$。

**样例 #1 解释** 给定的字符串为 `ba`、`abc` 和 `cbaa`。 例如，分别使用一次 `ba` 和 `abc`，总代价为 $7$。按照 `abc`、`ba` 的顺序拼接，可以得到一个回文串。 此外，分别使用一次 `abc` 和 `cbaa`，总代价为 $9$。按照 `cbaa`、`abc` 的顺序拼接，也可以得到一个回文串。 由于无法以小于 $7$ 的代价构造回文串，因此输出 $7$。 **样例 #2 解释** 使用一次 `abcab` 和两次 `cba`，按照 `abcab`、`cba`、`cba` 的顺序拼接，可以得到一个回文串，总代价为 $11$。 **样例 #3 解释** 只使用一次 `a` 就可以得到一个回文串，但拼接 `ab` 和 `cba` 的代价更小。 **样例 #4 解释** 无法构造出回文串，因此输出 $-1$。 **数据范围** - $1\le N\le 50$ - $1\le |S_i|\le 20$ - $S_i$ 仅由小写英文字母组成。 - $1\le C_i\le 10^9$