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: import sys
  
  INF = 1 << 60
  MOD = 10**9 + 7  # 998244353
  sys.setrecursionlimit(2147483647)
  input = lambda: sys.stdin.readline().rstrip()
  from itertools import product
  from heapq import heappop, heappush
  
  
  def resolve():
      n = int(input())
      S = [None] * n
      C = [None] * n
      for i in range(n):
          S[i], C[i] = input().split()
          C[i] = int(C[i])
      for i in range(n):
          S.append(S[i][::-1])
          C.append(C[i])
  
      # id[i][j] : index of S[i][j:]
      id = [[] for _ in range(2 * n)]
      N = 1
      for i in range(2 * n):
          for j in range(len(S[i])):
              id[i].append(N)
              N += 1
  
      # make graph
      E = [[] for _ in range(N)]
      for i, ni in product(range(2 * n), repeat=2):
          if i // n == ni // n:
              continue
          for j in range(len(S[i])):
              now = S[i][j:]
              edge = S[ni]
              l = min(len(now), len(edge))
              if now[:l] != edge[:l]:
                  continue
              nv = None
              if len(now) > len(edge):
                  E[id[i][j]].append((id[i][j + len(edge)], C[ni]))
              elif len(now) < len(edge):
                  E[id[i][j]].append((id[ni][len(now)], C[ni]))
              else:
                  E[id[i][j]].append((0, C[ni]))
  
      # Dijkstra
      dist = [INF] * N
      queue = []
      for i, c in enumerate(C):
          dist[id[i][0]] = c
          heappush(queue, (c, id[i][0]))
      while queue:
          d, v = heappop(queue)
          if d != dist[v]:
              continue
          for nv, w in E[v]:
              if dist[nv] > d + w:
                  dist[nv] = d + w
                  heappush(queue, (d + w, nv))
  
      ans = dist[0]
      for i in range(2 * n):
          for j in range(len(S[i])):
              T = S[i][j:]
              if T == T[::-1]:
                  ans = min(ans, dist[id[i][j]])
  
      if ans == INF:
          ans = -1
      print(ans)
  
  
  resolve()
  
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."}]