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
  import queue
  
  input_methods = ["clipboard", "file", "key"]
  using_method = 0
  input_method = input_methods[using_method]
  
  tin = lambda: map(int, input().split())
  lin = lambda: list(tin())
  mod = 1000000007
  
  # +++++
  
  
  def is_kaibun(s):
      if len(s) <= 1:
          return True
      for c, cc in zip(s, s[::-1]):
          if c != cc:
              return False
      return True
  
  
  def mk_sub(s, other, s_is_front):
      # pa((s,other,s[:len(other)],other[:len(s)]))
      if len(s) <= len(other) and s == other[: len(s)]:
          return True, other[len(s) :], not s_is_front
      elif len(s) > len(other) and s[: len(other)] == other:
          return True, s[len(other) :], s_is_front
      return False, "", False
  
  
  def main():
      n = int(input())
      # b , c = tin()
      # s = input()
      dd_f = {}
      dd_b = {}
      for _ in range(n):
          s, v = input().split()
          v = int(v)
          if s in dd_f:
              v = min(v, dd_f[s])
          dd_f[s] = v
          dd_b[s[::-1]] = v
      front = True
      open_list = queue.PriorityQueue()
      close_list_f = set()
      close_list_b = set()
      for k in dd_f:
          open_list.put((dd_f[k], (k, front)))
  
      while not open_list.empty():
          # pa('rrrr')
          # return
          cost, (s, is_front) = open_list.get()
          # pa((cost,s,is_front))
          # pa(s if is_front else s[::-1])
          if is_kaibun(s):
              return cost
          if (is_front and s in close_list_f) or (not is_front and s in close_list_b):
              continue
          if is_front:
              close_list_f.add(s)
          else:
              close_list_b.add(s)
  
          dic = dd_b if is_front else dd_f
          for k in dic:
              is_ok, next_s, r_is_front = mk_sub(s, k, is_front)
              # pa((is_ok,next_s,r_is_front,k))
              if not is_ok:
                  continue
              elif r_is_front and next_s in close_list_f:
                  continue
              elif not r_is_front and next_s in close_list_b:
                  continue
              else:
                  open_list.put((cost + dic[k], (next_s, r_is_front)))
  
      return -1
  
  
  # +++++
  isTest = False
  
  
  def pa(v):
      if isTest:
          print(v)
  
  
  def input_clipboard():
      import clipboard
  
      input_text = clipboard.get()
      input_l = input_text.splitlines()
      for l in input_l:
          yield l
  
  
  if __name__ == "__main__":
      if sys.platform == "ios":
          if input_method == input_methods[0]:
              ic = input_clipboard()
              input = lambda: ic.__next__()
          elif input_method == input_methods[1]:
              sys.stdin = open("inputFile.txt")
          else:
              pass
          isTest = True
      else:
          pass
          # input = sys.stdin.readline
  
      ret = main()
      if ret is not None:
          print(ret)
  
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."}]