分数: 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.