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: class Dijkstra:
      class Edge:
          def __init__(self, _to, _cost):
              self.to = _to
              self.cost = _cost
  
      def __init__(self, V):
          self.G = [[] for i in range(V)]
          self._E = 0
          self._V = V
  
      @property
      def E(self):
          return self._E
  
      @property
      def V(self):
          return self._V
  
      def add(self, _from, _to, _cost):
          self.G[_from].append(self.Edge(_to, _cost))
          self._E += 1
  
      def shortest_path(self, start):
          import heapq
  
          que = []
          d = [float("inf")] * self.V
  
          for s in start:
              d[s] = 0
              heapq.heappush(que, (0, s))
  
          while len(que) != 0:
              cost, v = heapq.heappop(que)
              if d[v] < cost:
                  continue
  
              for i in range(len(self.G[v])):
                  e = self.G[v][i]
                  if d[e.to] > d[v] + e.cost:
                      d[e.to] = d[v] + e.cost
                      heapq.heappush(que, (d[e.to], e.to))
          return d
  
  
  N = int(input())
  string = []
  for i in range(N):
      s, c = input().split()
      string.append((s, int(c)))
  
  node = [(0, ""), (1, "")]
  for s, c in string:
      for j in range(len(s)):
          node.append((0, s[j:]))
      for j in range(len(s) - 1, -1, -1):
          node.append((1, s[: j + 1]))
  
  node = list(set(node))
  
  iddata = {i: e for e, i in enumerate(node)}
  n = len(iddata)
  edge = [[] for i in range(n)]
  for i in range(n):
      if node[i][0] == 0:
          S = node[i][1]
          for s, c in string:
              if len(s) <= len(S):
                  check = all(S[j] == s[-j - 1] for j in range(len(s)))
                  if check:
                      if len(s) == len(S):
                          next_node = (0, "")
                      else:
                          next_node = (0, S[len(s) :])
                      next_id = iddata[next_node]
                      edge[i].append((next_id, c))
              else:
                  check = all(S[j] == s[-j - 1] for j in range(len(S)))
                  if check:
                      if len(s) == len(S):
                          next_node = (1, "")
                      else:
                          next_node = (1, s[: len(s) - len(S)])
                      next_id = iddata[next_node]
                      edge[i].append((next_id, c))
      else:
          S = node[i][1]
          for s, c in string:
              if len(s) <= len(S):
                  check = all(s[j] == S[-j - 1] for j in range(len(s)))
                  if check:
                      if len(s) == len(S):
                          next_node = (1, "")
                      else:
                          next_node = (1, S[: len(S) - len(s)])
                      next_id = iddata[next_node]
                      edge[i].append((next_id, c))
              else:
                  check = all(s[j] == S[-j - 1] for j in range(len(S)))
                  if check:
                      if len(s) == len(S):
                          next_node = (0, "")
                      else:
                          next_node = (0, s[len(S) :])
                      next_id = iddata[next_node]
                      edge[i].append((next_id, c))
  
  palindrome = Dijkstra(n + 1)
  for i in range(n):
      for j, c in edge[i]:
          palindrome.add(j, i, c)
  
  start = []
  for i in range(n):
      s = node[i][1]
      if len(s) == 0:
          start.append(i)
      else:
          check = all(s[j] == s[-1 - j] for j in range(len(s)))
          if check:
              start.append(i)
  
  for s, c in string:
      id = iddata[0, s]
      palindrome.add(id, n, c)
      id = iddata[1, s]
      palindrome.add(id, n, c)
  
  res = palindrome.shortest_path(start)
  ans = res[n]
  
  # print(list(map(lambda x:node[x],start)))
  # for i in range(n):
  # if node[i][1]=="abc":
  # print(node[i])
  # print(list(map(lambda x:(node[x[0]],x[1]),edge[i])))
  
  if ans != float("inf"):
      print(ans)
  else:
      print(-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."}]