5067. 单词游戏

单点时限: 1.0 sec

内存限制: 512 MB

阿屈和室友蓬蓬最近在玩一种单词游戏,游戏规则如下:
- 开始时会给出 $N$ 个单词 $S_1, S_2, …, S_N$
- 每个玩家选择至少一个单词(可以重复选则某个单词 $S_i$),拼接形成回文串
- 率先得到回文串的玩家获胜

蓬蓬发现他每次都打不过阿屈,于是他修改了游戏规则:
- 每个单词 $S_i$ 赋予一个值 $1\le C_i \le 10^9$,每选择一次 $S_i$ 就要付出 $C_i$ 的代价
- 构成回文串且所用代价最小的玩家获胜

阿屈虽然能很快得到回文串,但却不擅长得到最小代价回文串,这撼动了他在单词游戏中的统治地位。你能帮助阿屈计算出构成回文串的最小代价吗?

输入格式

第一行一个正整数 $N$ ($1\le N \le 100$)。

接下来 $N$ 行,每行一个字符串 $S_i$ ($1\le |S_i| \le 60$) 以及一个正整数 $C_i$ ($1\le C_i \le 10^9$) 表示选择该字符串的代价。

输出格式

输出一个正整数 cost,表示阿屈用所给单词 $S_1, S_2, …, S_N$ 构成回文串的最小代价。若无法构成回文串,输出 -1。

样例

Input
4
ab 5
cba 3
a 12
ab 10
Output
8
Input
2
abc 1
ab 2
Output
-1
Input
2
abcab 5
cba 3
Output
11

提示

  • $1\le N\le100$

  • $1\le|S_i|\le 60$

  • $1\le C_i \le 10^9$

  • $S_i$ 只包含小写字母

在样例 1 中,可以选择 a 直接构成回文串,所需代价为 12,但选择 abcba 构成回文串 abcba 的代价为 8。

在样例 2 中,无法构成回文串,输出 -1。

在样例 3 中,选择 abcab 一次、cba 两次,构成回文串 abcab|cba|cba,最小代价为 11。

24 人解决,34 人已尝试。

29 份提交通过,共有 142 份提交。

5.2 EMB 奖励。

创建: 1 年,7 月前.

修改: 1 年,7 月前.

最后提交: 8 月,1 周前.

来源: N/A

题目标签