output_description: Print the minimum total cost needed to choose strings so that Takahashi can
  make a palindrome, or -1 if there is no such choice.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      S_1 C_1
      S_2 C_2
      :
      S_N C_N
attempt: 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, 99999999999999):
                          rdpp[ns] = min(rdpp[ns], v + cs[p])
                  elif s.startswith(k):
                      ns = s[len(k) :]
                      if v + cs[p] < dp.get(ns, 99999999999999):
                          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 < 9999999999 else -1)
  
problem_description: 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.
samples: [{"input": "3\n    ba 3\n    abc 4\n    cbaa 5", "output": "7\n    \n\nWe have `ba`, `abc`, and `cbaa`.\n\nFor example, we can use `ba` once and `abc` once for a cost of 7, then\nconcatenate them in the order `abc`, `ba` to make a palindrome. Also, we can\nuse `abc` once and `cbaa` once for a cost of 9, then concatenate them in the\norder `cbaa`, `abc` to make a palindrome.\n\nWe cannot make a palindrome for a cost less than 7, so we should print 7.\n\n* * *"}, {"input": "2\n    abcab 5\n    cba 3", "output": "11\n    \n\nWe can choose `abcab` once and `cba` twice, then concatenate them in the order\n`abcab`, `cba`, `cba` to make a palindrome for a cost of 11.\n\n* * *"}, {"input": "4\n    ab 5\n    cba 3\n    a 12\n    ab 10", "output": "8\n    \n\nWe can choose `a` once, which is already a palindrome, but it is cheaper to\nconcatenate `ab` and `cba`.\n\n* * *"}, {"input": "2\n    abc 1\n    ab 2", "output": "-1\n    \n\nWe cannot make a palindrome, so we should print -1."}]