Making Palindrome

题目描述

我们有 $N$ 个由小写英文字母组成的字符串：$S_1, S_2, \cdots, S_N$。 Takahashi 想通过选择一个或多个这些字符串（可以多次选择同一个字符串）并以他选择的某种顺序将它们连接起来，得到一个回文字符串。 使用字符串 $S_i$ 一次的代价是 $C_i$，多次使用的代价是 $C_i$ 乘以使用次数。 求使 Takahashi 能构成回文字符串所需的最小总代价。 如果不存在可以构成回文的字符串选择，输出 $-1$。

输入格式

输入按下列格式由标准输入给出： $N$ $S_1$ $C_1$ $S_2$ $C_2$ : $S_N$ $C_N$

输出格式

打印使 Takahashi 能构成回文字符串的最小总代价；如果不存在这样的选择，则打印 $-1$。

3
ba 3
abc 4
cbaa 5

7

2
abcab 5
cba 3

11

4
ab 5
cba 3
a 12
ab 10

8

2
abc 1
ab 2

-1

提示

$1 \leq N \leq 50$ $1 \leq |S_i| \leq 20$ $S_i$ 由小写英文字母组成。 $1 \leq C_i \leq 10^9$我们有 $ba$、$abc$ 和 $cbaa$。 例如，我们可以使用 $ba$ 一次和 $abc$ 一次，代价为 $7$，然后按顺序将它们连接为 $abc$, $ba$ 以得到回文。 另外，我们可以使用 $abc$ 一次和 $cbaa$ 一次，代价为 $9$，然后按顺序将它们连接为 $cbaa$, $abc$ 以得到回文。 无法以小于 $7$ 的代价构成回文，因此应输出 $7$。
我们可以选择 $abcab$ 一次和 $cba$ 两次，然后按顺序将它们连接为 $abcab$, $cba$, $cba$ 以得到回文，代价为 $11$。
我们可以选择 $a$ 一次，它本身就是回文，但通过连接 $ab$ 和 $cba$ 更便宜。
我们无法构成回文，因此应输出 $-1$。

标签: AtCoder|abc175F

来源

AtCoder|abc175F