F - 构建回文串

得分：$600$ 分

题目描述

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

Takahashi 想要选择其中一个或多个字符串来构建一个回文串 - 同一个字符串可以选择多次，并且可以按照他的选择顺序进行拼接。

使用字符串 $S_i$ 一次的花费是 $C_i$，多次使用的花费是 $C_i$ 乘以使用次数。

找出选择字符串使得 Takahashi 可以构建回文串所需的最小总花费。

如果没有选择字符串使得他可以构建回文串，则输出 $-1$。

约束

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

输入

输入通过标准输入给出，格式如下：

$N$

$S_1$ $C_1$

$S_2$ $C_2$

$:$

$S_N$ $C_N$

输出

输出选择字符串使得 Takahashi 可以构建回文串所需的最小总花费，如果没有就输出 $-1$。

3
ba 3
abc 4
cbaa 5

7

我们有 ba，abc 和 cbaa。

例如，我们可以使用 ba 一次和 abc 一次，总花费为 $7$，然后按照顺序拼接它们 abc，ba 来构建一个回文串。 同样地，我们可以使用 abc 一次和 cbaa 一次，总花费为 $9$，然后按照顺序拼接它们 cbaa，abc 来构建一个回文串。

我们无法以小于 $7$ 的花费构建回文串，所以我们应该输出 $7$。

2
abcab 5
cba 3

11

我们可以选择 abcab 一次和 cba 两次，然后按照顺序拼接它们 abcab，cba，cba 来构建一个花费为 $11$ 的回文串。

4
ab 5
cba 3
a 12
ab 10

8

我们可以选择 a 一次，因为它本身就是一个回文串，但是拼接 ab 和 cba 更便宜。

2
abc 1
ab 2

-1

我们无法构建回文串，所以应该输出 $-1$。