Contest Duration: - (local time) (100 minutes) Back to Home
F - Making Palindrome /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

また、どのように選んでも回文を作ることが不可能である場合は -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

3
ba 3
abc 4
cbaa 5


出力例 1

7


ba, abc, cbaa があります。

コスト 7 未満で回文を作ることはできないので、7 を出力してください。

入力例 2

2
abcab 5
cba 3


出力例 2

11


abcab1 個、cba2 個選んで、abcab, cba, cba の順で連結すると回文になり、コストは 11 です。

入力例 3

4
ab 5
cba 3
a 12
ab 10


出力例 3

8


a1 個だけ選んで回文とすることもできますが、abcba を選んで連結する方がコストが小さいです。

入力例 4

2
abc 1
ab 2


出力例 4

-1


Score : 600 points

Problem Statement

We have N strings of lowercase English letters: S_1, S_2, \cdots, S_N.

Takahashi wants to make a string that is a palindrome by choosing one or more of these strings - the same string can be chosen more than once - and concatenating them in some order of his choice.

The cost of using the string S_i once is C_i, and the cost of using it multiple times is C_i multiplied by that number of times.

Find the minimum total cost needed to choose strings so that Takahashi can make a palindrome.

If there is no choice of strings in which he can make a palindrome, print -1.

Constraints

• 1 \leq N \leq 50
• 1 \leq |S_i| \leq 20
• S_i consists of lowercase English letters.
• 1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
S_1 C_1
S_2 C_2
:
S_N C_N


Output

Print the minimum total cost needed to choose strings so that Takahashi can make a palindrome, or -1 if there is no such choice.

Sample Input 1

3
ba 3
abc 4
cbaa 5


Sample Output 1

7


We have ba, abc, and cbaa.

For example, we can use ba once and abc once for a cost of 7, then concatenate them in the order abc, ba to make a palindrome. Also, we can use abc once and cbaa once for a cost of 9, then concatenate them in the order cbaa, abc to make a palindrome.

We cannot make a palindrome for a cost less than 7, so we should print 7.

Sample Input 2

2
abcab 5
cba 3


Sample Output 2

11


We can choose abcab once and cba twice, then concatenate them in the order abcab, cba, cba to make a palindrome for a cost of 11.

Sample Input 3

4
ab 5
cba 3
a 12
ab 10


Sample Output 3

8


We can choose a once, which is already a palindrome, but it is cheaper to concatenate ab and cba.

Sample Input 4

2
abc 1
ab 2


Sample Output 4

-1


We cannot make a palindrome, so we should print -1.