问题陈述

我们有 $N$ 个由小写英文字母组成的字符串：$S_1, S_2, \cdots, S_N$。

高桥想通过选择其中一个或多个字符串（可以重复选择同一个字符串），并按他自己选择的顺序将它们连接起来，使得得到的字符串是一个回文字符串。

使用字符串 $S_i$ 一次的费用是 $C_i$，使用多次的费用是 $S_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$。