2023 年上海市大学生程序设计竞赛 - 四月赛

输入格式

第一行一个正整数 $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,\dots ,S_N$ 构成回文串的最小代价。若无法构成回文串，输出 -1。

4
ab 5
cba 3
a 12
ab 10

8

2
abc 1
ab 2

-1

2
abcab 5
cba 3

11

提示

• $1\le N\le 100$

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

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

• $S_i$ 只包含小写字母

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

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

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