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-----
3
ba 3
abc 4
cbaa 5

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    N = int(input())
    S = []
    R = []
    C = []
    for _ in range(N):
        s, c = input().strip().split()
        S.append(s)
        R.append(s[::-1])
        C.append(int(c))
    
    vis = set()
    mem = dict()

    def dp(s, p):
        if (s, p) in mem: return mem[s, p]
        if s == s[::-1]: return 0
        if (s, p) in vis: return INF

        ans = INF
        vis.add((s, p))
        for i, t in enumerate(S if p else R):
            if len(t) >= len(s) and t.startswith(s):
                ans = min(ans, dp(t[len(s):], p ^ 1) + C[i])
            elif len(s) > len(t) and s.startswith(t):
                ans = min(ans, dp(s[len(t):], p) + C[i])
        vis.discard((s, p))
        mem[s, p] = ans
        return ans
        
    ans = INF
    for i in range(N):
        ans = min(ans, dp(S[i], 0) + C[i])
    return -1 if ans == INF else ans


def __starting_point():
    ans = solve()
    print(ans)
__starting_point()

import sys
sys.setrecursionlimit(10**9)

INF = 10**12
LIM = 20
N = int(input())
D = dict()
for _ in range(N):
    s, c = input().split()
    if s in list(D.keys()):
        D[s] = min(D[s], int(c))
    else:
        D[s] = int(c)

def check_kaibun(s):
    n = len(s)
    return all(s[i] == s[-i-1] for i in range(n//2))

def calc_cost(use):
    return sum(D[s] * n for (s, n) in list(use.items()))

def find_candidate(cost, use, s, is_left):
    if check_kaibun(s):
        return min(cost, calc_cost(use))

    if is_left:
        for t in list(D.keys()):
            # reversed s is included in the end of t
            if t[::-1].find(s) == 0:
                use[t] += 1
                if use[t] > LIM:
                    return INF
                c = find_candidate(cost, use, t[:-len(s):], False)
                cost = min(cost, c)
                use[t] -= 1
            # reveresed t is included in the begin of s
            elif s.find(t[::-1]) == 0:
                use[t] += 1
                c = find_candidate(cost, use, s[len(t):], True)
                cost = min(cost, c)
                use[t] -= 1
    else:
        for t in list(D.keys()):
            # t is included in the end of reversed s
            if s[::-1].find(t) == 0:
                use[t] += 1
                c = find_candidate(cost, use, s[:-len(t):], False)
                cost = min(cost, c)
                use[t] -= 1
            # s is included in the begin of reveresed t
            elif t.find(s[::-1]) == 0:
                use[t] += 1
                c = find_candidate(cost, use, t[len(s):], True)
                cost = min(cost, c)
                use[t] -= 1

    return min(cost, INF)

def solve():
    ans = INF
    for s in list(D.keys()):
        use = {s: 0 for s in list(D.keys())}
        use[s] = 1
        ans = find_candidate(ans, use, s, True)
    return ans if ans < INF else -1

def __starting_point():
    print((solve()))

__starting_point()

from heapq import heapify, heappop, heappush


def rolling(s):
    """
    文字列 [i, j] のハッシュ
    j < i の場合は逆順
    """
    n = len(s)
    ret = [[0] * n for _ in range(n)]

    for i in range(n):
        rh = 0
        for j in range(i, n):
            b = ord(s[j]) - 96
            rh = rh * 27 + b
            ret[i][j] = rh

    for j in range(n):
        rh = 0
        for i in range(j, -1, -1):
            b = ord(s[i]) - 96
            rh = rh * 27 + b
            ret[j][i] = rh

    return ret


def solve(n, sss, ccc, rhs):
    INF = 10 ** 18
    ans = INF
    q = []
    for i in range(n):
        s = sss[i]
        c = ccc[i]
        l = len(s)

        q.append((c, 0, i, 0))
        q.append((c, 1, i, l - 1))

        for j in range(l):
            k = 1
            while j - k >= 0 and j + k < l:
                if s[j - k] != s[j + k]:
                    break
                k += 1
            else:
                if j - k == -1 and j + k == l:
                    ans = min(ans, c)
                elif j - k == -1:
                    q.append((c, 0, i, j + k))
                else:
                    q.append((c, 1, i, j - k))

        for j in range(l - 1):
            k = 0
            while j - k >= 0 and j + k + 1 < l:
                if s[j - k] != s[j + k + 1]:
                    break
                k += 1
            else:
                if j - k == -1 and j + k + 1 == l:
                    ans = min(ans, c)
                elif j - k == -1:
                    q.append((c, 0, i, j + k + 1))
                else:
                    q.append((c, 1, i, j - k))

    heapify(q)

    checked = []
    for s in sss:
        checked.append([[False, False] for _ in range(len(s))])

    while q:
        cost, fb, i, j = heappop(q)
        if cost >= ans:
            break
        if checked[i][j][fb]:
            continue
        s = sss[i]
        ls = len(s)
        lm = ls - j if fb == 0 else j + 1
        checked[i][j][fb] = True
        rhr = rhs[i][j]

        if fb == 0:
            for ti in range(n):
                t = sss[ti]
                lt = len(t)
                if lm == lt:
                    if rhs[ti][-1][0] == rhr[-1]:
                        ans = min(ans, cost + ccc[ti])
                elif lm > lt:
                    if rhs[ti][-1][0] == rhr[j + lt - 1]:
                        heappush(q, (cost + ccc[ti], 0, i, j + lt))
                else:
                    if rhs[ti][-1][lt - lm] == rhr[-1]:
                        heappush(q, (cost + ccc[ti], 1, ti, lt - lm - 1))
        else:
            for ti in range(n):
                t = sss[ti]
                lt = len(t)
                if lm == lt:
                    if rhs[ti][0][-1] == rhr[0]:
                        ans = min(ans, cost + ccc[ti])
                elif lm > lt:
                    if rhs[ti][0][-1] == rhr[j - lt + 1]:
                        heappush(q, (cost + ccc[ti], 1, i, j - lt))
                else:
                    if rhs[ti][0][lm - 1] == rhr[0]:
                        heappush(q, (cost + ccc[ti], 0, ti, lm))

    if ans == INF:
        return -1
    else:
        return ans


n = int(input())
sss = []
ccc = []
rhs = []
for si in range(n):
    s, c = input().split()
    sss.append(s)
    ccc.append(int(c))
    rhs.append(rolling(s))

print((solve(n, sss, ccc, rhs)))


from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 60
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
done = [set(), set()]
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        break
    d, s, c = D[r]
    if s in done[d]: continue
    done[d].add(s)
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

import sys
input = sys.stdin.readline

N=int(input())
ST=[input().split() for i in range(N)]

for i in range(N):
    ST[i][1]=int(ST[i][1])

ST.sort()

ST2=[]
for i in range(N):
    if i>0 and ST[i][0]==ST[i-1][0]:
        continue
    ST2.append((ST[i][0],ST[i][1]))
ST=ST2


FDICT=dict()
BDICT=dict()

for s,i in ST:
    FDICT[s[::-1]]=i
    BDICT[s[::-1]]=i

    for j in range(1,len(s)):
        if not(s[:j][::-1] in BDICT):
            BDICT[s[:j][::-1]]=1<<60
        if not(s[-j:][::-1] in FDICT):
            FDICT[s[-j:][::-1]]=1<<60

ANS=1<<60
flag=0
for rep in range(1<<60):
    flag=0
    for f in FDICT:
        lf=len(f)
        for s,i in ST:
            ls=len(s)

            if lf == ls:
                if s==f:
                    ANS=min(ANS,FDICT[f]+i)
            elif ls>lf:
                if s[-lf:]==f and BDICT[s[:-lf][::-1]]>FDICT[f]+i:
                    BDICT[s[:-lf][::-1]]=FDICT[f]+i
                    flag=1
            else:
                if f[-ls:]==s and FDICT[f[:-ls]]>FDICT[f]+i:
                    FDICT[f[:-ls]]=FDICT[f]+i
                    flag=1
                    

    for b in BDICT:
        lb=len(b)
        for s,i in ST:
            ls=len(s)

            if lb == ls:
                if s==b:
                    ANS=min(ANS,BDICT[b]+i)
            elif ls>lb:
                if s[:lb]==b and FDICT[s[lb:][::-1]]>BDICT[b]+i:
                    FDICT[s[lb:][::-1]]=BDICT[b]+i
                    flag=1
                    
            else:
                if b[:ls]==s and BDICT[b[ls:]]>BDICT[b]+i:
                    BDICT[b[ls:]]=BDICT[b]+i
                    flag=1
    if flag==0:
        break
                    

for f in FDICT:
    if f==f[::-1]:
        ANS=min(ANS,FDICT[f])

for b in BDICT:
    if b==b[::-1]:
        ANS=min(ANS,BDICT[b])

if ANS==1<<60:
    print((-1))
else:
    print(ANS)


'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n = int(ipt())
    wrds = []
    hq = []
    usd = set()
    for i in range(n):
        s,c = input().split()
        c = int(c)
        wrds.append((s,c))
        hpq.heappush(hq,(c,s,1))

    while hq:
        hc,hs,hp = hpq.heappop(hq)
        usd.add((hs,hp))
        ls = len(hs)
        if hs == hs[::-1]:
            print(hc)
            return
        for si,ci in wrds:
            lsi = len(si)
            if lsi > ls:
                if hp == 1:
                    wt = si[::-1]
#                    print(wt)
                    if hs == wt[:ls:] and not (wt[ls::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,wt[ls::],-1))
                else:
                    if hs == si[:ls:] and not (si[ls::],1) in usd:
                        hpq.heappush(hq,(hc+ci,si[ls::],1))
            else:
                if hp == 1:
                    wt = si[::-1]
                    if wt == hs[:lsi:] and not (hs[lsi::],1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[lsi::],1))
                else:
                    if si == hs[:lsi:] and not (hs[lsi::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[lsi::],-1))
#        print(hq)

    print((-1))


    return None

def __starting_point():
    main()

__starting_point()

from collections import defaultdict
from heapq import heappush, heappop, heapify
def main():
    N = int(input())
    SC = []
    SCrev = []
    for _ in range(N):
        s, c = input().split()
        c = int(c)
        SC.append((s, c))
        SCrev.append((s[::-1], c))
    dist = defaultdict(lambda: 10**18)
    q = [(c, s, "") for s, c in SC] + [(c, "", s) for s, c in SCrev]
    for c, l, r in q:
        dist[(l, r)] = min(dist[(l, r)], c)
    heapify(q)
    while q:
        dist_v, vl, vr = heappop(q)
        if (vl == vr == "") or (len(vl) and vl == vl[::-1]) or (len(vr) and vr == vr[::-1]):
            print(dist_v)
            return
        if dist[(vl, vr)] != dist_v:
            continue
        if len(vl) < len(vr):
            for s, c in SC:
                if len(s) <= len(vr):
                    if vr.startswith(s):
                        vr_ = vr[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
                else:
                    if s.startswith(vr):
                        vl_ = s[len(vr):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
        else:
            for s, c in SCrev:
                if len(s) <= len(vl):
                    if vl.startswith(s):
                        vl_ = vl[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
                else:
                    if s.startswith(vl):
                        vr_ = s[len(vl):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
    print((-1))

main()


it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    N = int(input())
    S = []
    C = []
    for _ in range(N):
        s, c = input().strip().split()
        S.append(s)
        C.append(int(c))
    
    vis = set()
    mem = dict()

    def dp(s, p):
        if (s, p) in mem:
            return mem[s, p]

        if s == s[::-1]:
            return 0

        if (s, p) in vis:
            return INF

        vis.add((s, p))

        ans = INF
        if p == 0:
            for i in range(N):
                if len(S[i]) >= len(s):
                    if S[i][::-1].startswith(s):
                        ans = min(ans, dp(S[i][:-len(s)], 1) + C[i])
                else:
                    if s.startswith(S[i][::-1]):
                        ans = min(ans, dp(s[len(S[i]):], 0) + C[i])
        else:
            for i in range(N):
                if len(S[i]) >= len(s):
                    if S[i].startswith(s[::-1]):
                        ans = min(ans, dp(S[i][len(s):], 0) + C[i])
                else:
                    if s[::-1].startswith(S[i]):
                        ans = min(ans, dp(s[:-len(S[i])], 1) + C[i])

        vis.discard((s, p))
        mem[s, p] = ans
        return ans
        
    ans = INF
    for i in range(N):
        ans = min(ans, dp(S[i], 0) + C[i])
    return -1 if ans == INF else ans


def __starting_point():
    ans = solve()
    print(ans)
__starting_point()