Problem:
 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 .

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
ss = []
cs = []
for i in range(n):
    s, c = stdin.readline().split()
    ss.append(s)
    cs.append(int(c))

dp = defaultdict(lambda: 999999999999999)
rdp = defaultdict(lambda: 999999999999999)
p = 0
ved = set()
for s in ss:
    dp[s] = min(dp[s], cs[p])
    p += 1
    ved.add(s)

ans = 999999999999999

while True:
    dpp = defaultdict(lambda: 999999999999999)
    rdpp = defaultdict(lambda: 999999999999999)
    for k, v in dp.items():
        if k == k[::-1]:
            ans = min(ans, v)
        else:
            p = 0
            for s in ss:
                if k.startswith(s[::-1]):
                    ns = k[len(s):]
                    if v + cs[p] < dp.get(ns, 99999999999999):
                        dpp[ns] = min(dpp[ns], v + cs[p])
                elif s[::-1].startswith(k):
                    ns = s[::-1][len(k):]
                    if v + cs[p] < rdp.get(ns, 99999999999999):
                        rdpp[ns] = min(rdpp[ns], v + cs[p])
                p += 1
    for k, v in rdp.items():
        if k == k[::-1]:
            ans = min(ans, v)
        else:
            p = 0
            for s in ss:
                if k.startswith(s):
                    ns = k[len(s):]
                    if v + cs[p] < rdp.get(ns, 999999999999999):
                        rdpp[ns] = min(rdpp[ns], v + cs[p])
                elif s.startswith(k):
                    ns = s[len(k):]
                    if v + cs[p] < dp.get(ns, 999999999999999):
                        dpp[ns] = min(dpp[ns], v + cs[p])
                p += 1
    if len(dpp) + len(rdpp) == 0:
        break
    for k, v in dpp.items(): dp[k] = v
    for k, v in rdpp.items(): rdp[k] = v
print(ans if ans < 999999999999999 else -1)