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----- 3 ba 3 abc 4 cbaa 5

-----Sample Output----- 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.