制作回文

题目描述

有 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \cdots, S_N$。

高桥君首先从这些字符串中允许重复地选取合计 $1$ 个以上,然后将选出的字符串按任意顺序连接,试图构造一个回文字符串。

使用 $1$ 个字符串 $S_i$ 需要花费 $C_i$,即使是相同的字符串,使用几个就花费几份成本。

在能够按上述方法构造出回文的字符串选取方法中,求成本总和的最小值。

另外,如果无论如何选取都无法构造出回文,输出 $-1$。

输入格式

输入按以下格式从标准输入给出:

$N$
$S_1$ $C_1$
$S_2$ $C_2$
$:$
$S_N$ $C_N$

输出格式

在能够构造出回文的字符串选取方法中,输出成本总和的最小值。如果无法构造,输出 $-1$。

样例

3
ba 3
abc 4
cbaa 5

7

有 ba、abc、cbaa。

例如,各使用 1 个 ba 和 abc 时成本为 $7$,按 abc、ba 的顺序连接会得到回文。 另外,各使用 1 个 abc 和 cbaa 时成本为 $9$,按 cbaa、abc 的顺序连接会得到回文。

无法以低于 $7$ 的成本构造出回文,因此输出 $7$。

2
abcab 5
cba 3

11

选取 1 个 abcab 和 2 个 cba,按 abcab、cba、cba 的顺序连接会得到回文,成本为 $11$。

4
ab 5
cba 3
a 12
ab 10

8

也可以只选取 1 个 a 作为回文,但选取 ab 和 cba 并连接的成本更小。

2
abc 1
ab 2

-1

无法构造出回文,因此输出 $-1$。

数据范围

• $1 \leq N \leq 50$
• $1 \leq |S_i| \leq 20$
• $S_i$ 由小写英文字母组成
• $1 \leq C_i \leq 10^9$