← 返回题目列表

AtCoder · abc175_f

F. 制作回文

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有 N 小写英文字母字符串: S_1, S_2, \cdots, S_N.

Takahashi 想要通过选择一个或多个字符串(同一个字符串可以多次选择)并按照他选择的某种顺序连接它们来创建一个回文字符串。

使用字符串的成本 S_i 一次是 C_i,多次使用的成本为 C_i 乘以该次数。

求选择字符串所需的最小总成本,以便高桥可以生成回文。

如果没有选择可以构成回文的字符串,则打印 -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

输出

打印选择字符串所需的最低总成本,以便高桥可以制作回文,或者 -1 如果没有这样的选择。


示例输入 1

3
ba 3
abc 4
cbaa 5

示例输出 1

7

我们有 ba, abc,和 cbaa.

例如,我们可以使用 ba 一次并且 abc 一次,费用为 7,然后按顺序连接它们 abc, ba 制作回文。 另外,我们可以使用 abc 一次并且 cbaa 一次,费用为 9,然后按顺序连接它们 cbaa, abc 制作回文。

我们不能以低于 7,所以我们应该打印 7.


示例输入 2

2
abcab 5
cba 3

示例输出 2

11

我们可以选择 abcab 一次并且 cba 两次,然后按顺序连接 abcab, cba, cba 制作回文的成本为 11.


示例输入 3

4
ab 5
cba 3
a 12
ab 10

示例输出 3

8

我们可以选择 a 一次,这已经是回文,但连接起来更便宜 ab 和 cba.


示例输入 4

2
abc 1
ab 2

示例输出 4

-1

我们无法制作回文,所以我们应该打印 -1.