AtCoder Beginner Contest 175 - Making Palindrome

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: MEDIUM_HARD

Starter code:

Solutions:
N = int(input())
S = []
C = []
for _ in range(N):
	(s, c) = input().split()
	C.append(int(c))
	S.append(tuple((ord(c) - ord('a') for c in s)))
INF = 10 ** 30
dp = {}

def min_cost(l, r):
	if (l, r) in dp:
		return dp[l, r]
	if l and l == l[::-1]:
		dp[l, r] = 0
		return dp[l, r]
	if r and r == r[::-1]:
		dp[l, r] = 0
		return dp[l, r]
	dp[l, r] = INF
	if not l:
		for (c, s) in zip(C, S):
			if len(s) > len(r):
				if s[len(s) - len(r):] == r:
					dp[l, r] = min(dp[l, r], c + min_cost(s[:len(s) - len(r)][::-1], ()))
			elif len(s) == len(r):
				if s == r:
					dp[l, r] = min(dp[l, r], c)
			elif s == r[len(r) - len(s):]:
				dp[l, r] = min(dp[l, r], c + min_cost((), r[:len(r) - len(s)]))
	if not r:
		for (c, s) in zip(C, S):
			if len(s) > len(l):
				if s[:len(l)] == l:
					dp[l, r] = min(dp[l, r], c + min_cost((), s[len(l):][::-1]))
			elif len(s) == len(l):
				if s == l:
					dp[l, r] = min(dp[l, r], c)
			elif s == l[:len(s)]:
				dp[l, r] = min(dp[l, r], c + min_cost(l[len(s):], ()))
	return dp[l, r]
m = min_cost((), ())
for (s, c) in zip(S, C):
	if s == s[::-1]:
		m = min(m, c)
if m == INF:
	print(-1)
else:
	print(m)


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])
				elif 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])
				elif 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
ans = solve()
print(ans)


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
N = I()
data = SLL(N)
words = []
costs = []
nodes = {('', 0), ('', 1)}
best = INF
for d in data:
	word = d[0]
	cost = int(d[1])
	if word == word[::-1]:
		best = min(best, cost)
		continue
	words.append(word)
	costs.append(cost)
	for j in range(len(word)):
		nodes.add((word[:j + 1], 1))
		nodes.add((word[j:], 0))
graph = {k: [] for k in nodes}
graph['', 1].append((0, ('', 0)))
for k in nodes:
	amari = k[0]
	t = k[1]
	if amari == amari[::-1]:
		if amari:
			graph[k].append((0, ('', 0)))
	else:
		n = len(amari)
		for i in range(len(words)):
			word = words[i]
			cost = costs[i]
			if t == 0:
				if len(word) > n:
					if amari == word[::-1][:n]:
						graph[k].append((cost, (word[:-n], 1)))
				elif amari[:len(word)] == word[::-1]:
					graph[k].append((cost, (amari[len(word):], 0)))
			elif len(word) > n:
				if amari[::-1] == word[:n]:
					graph[k].append((cost, (word[n:], 0)))
			elif amari[::-1][:len(word)] == word:
				graph[k].append((cost, (amari[:-len(word)], 1)))

def dijkstra(graph, start, cost):
	N = len(graph)
	d = {k: INF for k in nodes}
	d[start] = cost
	f = {k: False for k in nodes}
	q = [(cost, start)]
	while q:
		(c, u) = heapq.heappop(q)
		if f[u]:
			continue
		d[u] = c
		f[u] = True
		for (c, v) in graph[u]:
			if not f[v]:
				heapq.heappush(q, (c + d[u], v))
	return d
for i in range(len(words)):
	word = words[i]
	cost = costs[i]
	best = min(best, dijkstra(graph, (word, 0), cost)['', 0])
	best = min(best, dijkstra(graph, (word, 1), cost)['', 0])
if best == INF:
	print(-1)
else:
	print(best)


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)
			exit()
		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_))
				elif 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_, ''))
				elif 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()


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	n = I()
	lis = []
	c = []
	rev = []
	for _ in range(n):
		(a, b) = input().split()
		b = int(b)
		a = list(a)
		lis.append(a)
		rev.append(a[::-1])
		c.append(b)
	res = defaultdict(lambda : float('inf'))
	q = [(0, [], [])]
	res[tuple(), tuple()] = 0
	while q:
		(d, pre, suf) = heappop(q)
		ns = pre + suf[::-1]
		if ns != [] and ns == ns[::-1]:
			print(d)
			return
		if len(pre) <= len(suf):
			k = suf[len(pre):]
			for i in range(n):
				s = lis[i]
				m = min(len(s), len(k))
				if k[:m] == s[:m]:
					npre = pre + s
					re = d + c[i]
					i = tuple(npre)
					j = tuple(suf)
					if re < res[i, j]:
						res[i, j] = re
						heappush(q, (re, npre, suf))
		else:
			k = pre[len(suf):]
			for i in range(n):
				s = rev[i]
				m = min(len(s), len(k))
				if k[:m] == s[:m]:
					nsuf = suf + s
					re = d + c[i]
					i = tuple(pre)
					j = tuple(nsuf)
					if re < res[i, j]:
						res[i, j] = re
						heappush(q, (re, pre, nsuf))
	print(-1)
	return
solve()


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
			elif 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
			elif 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)


import math
import itertools
import queue
import bisect
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]
alp = 'abcdefghijklmnopqrstuvwxyz'
INF = 1 << 32 - 1

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]
					if hs == wt[:ls] and (not (wt[ls:], -1) in usd):
						hpq.heappush(hq, (hc + ci, wt[ls:], -1))
				elif hs == si[:ls] and (not (si[ls:], 1) in usd):
					hpq.heappush(hq, (hc + ci, si[ls:], 1))
			elif hp == 1:
				wt = si[::-1]
				if wt == hs[:lsi] and (not (hs[lsi:], 1) in usd):
					hpq.heappush(hq, (hc + ci, hs[lsi:], 1))
			elif si == hs[:lsi] and (not (hs[lsi:], -1) in usd):
				hpq.heappush(hq, (hc + ci, hs[lsi:], -1))
	print(-1)
	return None

def __starting_point():
	main()
__starting_point()


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
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 = [[] 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
	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]
			if not (now.startswith(edge) or edge.startswith(now)):
				continue
			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]))
	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()


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()):
			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
			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()):
			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
			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 collections import deque

def isPalindrome(s):
	L = len(s)
	rst = True
	if L:
		for i in range(L // 2):
			if s[i] != s[L - 1 - i]:
				rst = False
				break
	return rst
N = int(input())
S = []
for _ in range(N):
	(s, c) = input().split()
	S.append((s, int(c)))
path = [dict() for _ in range(2)]
q = deque()
S.sort(key=lambda x: x[1])
for (s, c) in S:
	if s not in path[0] or path[0][s] > c:
		path[0][s] = c
		q.append((0, s, c))
ans = float('inf')
isPossible = False
while q:
	(side, s0, c0) = q.popleft()
	if isPalindrome(s0):
		ans = min(ans, c0)
		isPossible |= True
	else:
		for (s1, c1) in S:
			if side == 0:
				l = s0
				r = s1
			else:
				l = s1
				r = s0
			if len(l) > len(r):
				for i in range(len(r)):
					if l[i] != r[-1 - i]:
						break
				else:
					ns = l[len(r):]
					nc = c0 + c1
					nside = 0
					if ns not in path[nside] or path[nside][ns] > nc:
						path[nside][ns] = nc
						q.append((nside, ns, nc))
			elif len(l) < len(r):
				for i in range(len(l)):
					if l[i] != r[-1 - i]:
						break
				else:
					ns = r[:-len(l)]
					nc = c0 + c1
					nside = 1
					if ns not in path[nside] or path[nside][ns] > nc:
						path[nside][ns] = nc
						q.append((nside, ns, nc))
			else:
				for i in range(len(l)):
					if l[i] != r[-1 - i]:
						break
				else:
					ns = ''
					nc = c0 + c1
					nside = 0
					if ns not in path[nside] or path[nside][ns] > nc:
						path[nside][ns] = nc
						q.append((nside, ns, nc))
if isPossible:
	print(ans)
else:
	print(-1)


from collections import deque

def isPalindrome(s):
	L = len(s)
	return all((s[i] == s[L - 1 - i] for i in range(L // 2)))
N = int(input())
S = []
for _ in range(N):
	(s, c) = input().split()
	S.append((s, int(c)))
path = [dict() for _ in range(2)]
q = deque()
S.sort(key=lambda x: x[1])
for (s, c) in S:
	if s not in path[0] or path[0][s] > c:
		path[0][s] = c
		q.append((0, s, c))
INF = 10 ** 15
ans = INF
while q:
	(side, s0, c0) = q.popleft()
	if isPalindrome(s0):
		ans = min(ans, c0)
	else:
		for (s1, c1) in S:
			if side == 0:
				(l, r) = (s0, s1)
			else:
				(l, r) = (s1, s0)
			L = len(l)
			R = len(r)
			isCandidate = False
			if L > R:
				if all((l[i] == r[-1 - i] for i in range(R))):
					ns = l[len(r):]
					nc = c0 + c1
					nside = 0
					isCandidate |= True
			elif L < R:
				if all((l[i] == r[-1 - i] for i in range(L))):
					ns = r[:-len(l)]
					nc = c0 + c1
					nside = 1
					isCandidate |= True
			elif all((l[i] == r[-1 - i] for i in range(L))):
				ns = ''
				nc = c0 + c1
				nside = 0
				isCandidate |= True
			if isCandidate and (ns not in path[nside] or path[nside][ns] > nc):
				path[nside][ns] = nc
				q.append((nside, ns, nc))
if ans < INF:
	print(ans)
else:
	print(-1)


import sys, heapq, math
input = sys.stdin.readline
N = int(input())
SC = []
for _ in range(N):
	(S, C) = input().split()
	SC.append((S, int(C)))
nodes = dict()
nodes['S'] = []
for (s, c) in SC:
	for i in range(len(s) + 1):
		nodes['L' + s[i:]] = []
		nodes['R' + s[-i::-1]] = []
for node in nodes.keys():
	for (s, c) in SC:
		if node[0] == 'L':
			if s[::-1].startswith(node[1:]):
				nodes[node].append(('R' + s[-len(node)::-1], c))
			elif node[1:].startswith(s[::-1]):
				nodes[node].append(('L' + node[1 + len(s):], c))
		elif node[0] == 'R':
			if s.startswith(node[1:]):
				nodes[node].append(('L' + s[len(node) - 1:], c))
			elif node[1:].startswith(s):
				nodes[node].append(('R' + node[1 + len(s):], c))
for (s, c) in SC:
	nodes['S'].append(('L' + s, c))
	nodes['S'].append(('R' + s[::-1], c))
nodes['L'] = [('G', 0)]
nodes['R'] = [('G', 0)]
for node in nodes.keys():
	if len(node) != 1 and node[1:] == node[1:][::-1]:
		nodes[node].append(('G', 0))
HQ = [(0, 'S')]
heapq.heapify(HQ)
ans = -1
while len(HQ) > 0:
	(c, node) = heapq.heappop(HQ)
	if node == 'G':
		ans = c
		break
	for (node_, c_) in nodes[node]:
		heapq.heappush(HQ, (c + c_, node_))
	nodes[node] = []
print(ans)


from heapq import heappush, heappop
inf = float('inf')

def dijkstra(graph: list, node: int, start: int) -> list:
	dist = [inf] * node
	dist[start] = 0
	heap = [(0, start)]
	while heap:
		(cost, thisNode) = heappop(heap)
		for (NextCost, NextNode) in graph[thisNode]:
			dist_cand = dist[thisNode] + NextCost
			if dist_cand < dist[NextNode]:
				dist[NextNode] = dist_cand
				heappush(heap, (dist[NextNode], NextNode))
	return dist
N = int(input())
S1 = []
S2 = []
C = []
for i in range(N):
	(s, c) = input().split()
	S1.append(s)
	S2.append(s[::-1])
	C.append(int(c))
d_v = {('', ''): 0, ('l', ''): 1, ('r', ''): 2}
idx = 3
for i in range(N):
	s = S1[i]
	for j in range(len(s)):
		for k in range(j, len(s)):
			ss_l = s[j:k + 1]
			ss_r = ss_l[::-1]
			if ss_l != ss_r:
				if ('l', ss_l) not in d_v:
					d_v['l', ss_l] = idx
					idx += 1
				if ('r', ss_r) not in d_v:
					d_v['r', ss_r] = idx
					idx += 1
edge = [[] for _ in range(len(d_v))]
for i in range(N):
	s_l = S1[i]
	s_r = S2[i]
	c = C[i]
	for (lr, ss) in d_v:
		if ss == '':
			if lr == '':
				t = s_l
				if t == t[::-1]:
					t = ''
				edge[0].append((c, d_v['l', t]))
			else:
				continue
		if lr == 'l':
			if ss.startswith(s_r):
				t = ss[len(s_r):]
				if t == t[::-1]:
					t = ''
				edge[d_v[lr, ss]].append((c, d_v['l', t]))
			if s_r.startswith(ss):
				t = s_r[len(ss):]
				if t == t[::-1]:
					t = ''
				edge[d_v[lr, ss]].append((c, d_v['r', t]))
		elif lr == 'r':
			if ss.startswith(s_l):
				t = ss[len(s_l):]
				if t == t[::-1]:
					t = ''
				edge[d_v[lr, ss]].append((c, d_v['r', t]))
			if s_l.startswith(ss):
				t = s_l[len(ss):]
				if t == t[::-1]:
					t = ''
				edge[d_v[lr, ss]].append((c, d_v['l', t]))
dist = dijkstra(edge, len(d_v), 0)
ans = min(dist[1], dist[2])
if ans == inf:
	ans = -1
print(ans)


import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 31
N = int(readline())
ss = []
cs = []
for i in range(N):
	(s, c) = readline().decode().rstrip().split()
	ss.append(s)
	cs.append(int(c))
dp = defaultdict(lambda : INF)
rdp = defaultdict(lambda : INF)
p = 0
ved = set()
for s in ss:
	dp[s] = min(dp[s], cs[p])
	p += 1
	ved.add(s)
ans = INF
while True:
	dpp = defaultdict(lambda : INF)
	rdpp = defaultdict(lambda : INF)
	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, INF):
						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, INF):
						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, INF):
						rdpp[ns] = min(rdpp[ns], v + cs[p])
				elif s.startswith(k):
					ns = s[len(k):]
					if v + cs[p] < dp.get(ns, INF):
						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 < INF else -1)


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):
	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())
	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():
		(cost, (s, is_front)) = open_list.get()
		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)
			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 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
ret = main()
if ret is not None:
	print(ret)


import sys
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
sys.setrecursionlimit(10 ** 7)
INF = 1 << 50

def search_next(l, r, SC):
	(ll, lc) = l
	(rr, rc) = r
	nexts = []
	if len(ll) > len(rr):
		part = ll[::-1]
		for (s, c) in SC:
			if s[-len(part):] == part:
				r_n = (s[:-len(ll)], rc + c)
				l_n = ('', lc)
				nexts.append((rc + c + lc, (l_n, r_n)))
			elif s == part[-len(s):]:
				l_n = (ll[len(s):], lc)
				r_n = ('', rc + c)
				nexts.append((rc + c + lc, (l_n, r_n)))
	else:
		part = rr[::-1]
		for (s, c) in SC:
			if s[:len(part)] == part:
				l_n = (s[len(rr):], lc + c)
				r_n = ('', rc)
				nexts.append((lc + rc + c, (l_n, r_n)))
			elif s == part[:len(s)]:
				r_n = (rr[:-len(s)], rc)
				l_n = ('', lc + c)
				nexts.append((lc + rc + c, (l_n, r_n)))
	return nexts

def palindrome(l, r):
	if l + r == (l + r)[::-1]:
		return True
	else:
		return False

def run():
	totalL = 0
	N = int(sysread())
	SC = []
	for i in range(N):
		(s, c) = input().split()
		c = int(c)
		SC.append((s, c))
		totalL += len(s)
	min_val = INF
	for (s, c) in SC:
		queue = []
		left = (s, c)
		right = ('', 0)
		heappush(queue, (c, (left, right)))
		done = False
		count = 0
		while queue:
			count += 1
			if count > 200000:
				break
			(cost, (l, r)) = heappop(queue)
			if palindrome(l[0], r[0]):
				done = True
				break
			nexts = search_next(l, r, SC)
			for n in nexts:
				heappush(queue, n)
		if done:
			min_val = min(min_val, cost)
	if min_val == INF:
		print(-1)
	else:
		print(min_val)
run()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
from collections import defaultdict
ns = defaultdict(set)
sc = [None] * n
nodes = []
for i in range(n):
	(s, c) = input().split()
	c = int(c)
	sc[i] = (s, c)
	nodes.extend([(0, s[i:]) for i in range(len(s))])
	nodes.extend([(1, s[:i]) for i in range(1, len(s) + 1)])
for u in nodes:
	for (s, c) in sc:
		if u[0] == 0 and s.endswith(u[1][::-1]):
			v = (1, s[:-len(u[1])])
			ns[u].add((c, v))
		elif u[0] == 0 and u[1][::-1].endswith(s):
			v = (0, u[1][len(s):])
			ns[u].add((c, v))
		elif u[0] == 1 and s.startswith(u[1][::-1]):
			v = (0, s[len(u[1]):])
			ns[u].add((c, v))
		elif u[0] == 1 and u[1][::-1].startswith(s):
			v = (1, u[1][:-len(s)])
			ns[u].add((c, v))
start = 0
for (s, c) in sc:
	ns[start].add((c, (0, s)))
	ns[start].add((c, (1, s)))

def dijkstra(start):
	import heapq
	vals = {}
	h = [(0, start)]
	vals[start] = 0
	while h:
		(val, u) = heapq.heappop(h)
		for (d, v) in ns[u]:
			if v not in vals or vals[v] > val + d:
				vals[v] = val + d
				heapq.heappush(h, (vals[v], v))
	return vals
vals = dijkstra(start)
ans = float('inf')
for (k, v) in vals.items():
	if k == 0:
		continue
	if k[1] == k[1][::-1]:
		ans = min(ans, v)
if ans == float('inf'):
	ans = -1
print(ans)


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()
r = rand()
D[r] = (0, '', 0)
H = [r]
ans = 1 << K
while H:
	r = heappop(H)
	if r in done:
		continue
	done.add(r)
	if time() - sTime > 1.7:
		break
	(d, s, c) = D[r]
	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)
				elif 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)
				elif 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)


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, 999999999999999):
						rdpp[ns] = min(rdpp[ns], v + cs[p])
				elif s.startswith(k):
					ns = s[len(k):]
					if v + cs[p] < dp.get(ns, 999999999999999):
						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 < 999999999999999 else -1)


import sys
from heapq import heappush, heappop

def input():
	return sys.stdin.readline().strip()

def main():
	N = int(input())
	string = []
	cost = []
	for _ in range(N):
		(s, c) = input().split()
		string.append(s)
		cost.append(int(c))
	length = [len(string[i]) for i in range(N)]
	string_to_id = [[[0] * (length[i] + 1) for i in range(N)] for _ in range(2)]
	id_to_string = {}
	n = 1
	for d in range(2):
		for i in range(N):
			for j in range(1, length[i] + 1):
				string_to_id[d][i][j] = n
				id_to_string[n] = (d, i, j)
				n += 1
	repn = [[] for _ in range(n)]
	for i in range(N):
		repn[0].append((string_to_id[0][i][length[i]], cost[i]))
		repn[0].append((string_to_id[1][i][length[i]], cost[i]))
	for v in range(1, n):
		(d, i, j) = id_to_string[v]
		if d == 0:
			for ni in range(N):
				if j <= length[ni]:
					if string[ni][:j] != string[i][:j][::-1]:
						continue
					id = string_to_id[1][ni][length[ni] - j]
				else:
					if string[ni] != string[i][j - length[ni]:j][::-1]:
						continue
					id = string_to_id[0][i][j - length[ni]]
				repn[v].append((id, cost[ni]))
		else:
			for ni in range(N):
				if j <= length[ni]:
					if string[i][-j:][::-1] != string[ni][-j:]:
						continue
					id = string_to_id[0][ni][length[ni] - j]
				else:
					if string[i][-j:-j + length[ni]][::-1] != string[ni]:
						continue
					id = string_to_id[1][i][j - length[ni]]
				repn[v].append((id, cost[ni]))
	min_cost = [10 ** 18] * n
	q = []
	for (v, cos) in repn[0]:
		min_cost[v] = cos
		heappush(q, (cos, v))
	while q:
		(dist, v) = heappop(q)
		if min_cost[v] != dist:
			continue
		for (nv, ncos) in repn[v]:
			if min_cost[nv] <= dist + ncos:
				continue
			min_cost[nv] = dist + ncos
			heappush(q, (dist + ncos, nv))
	ans = 10 ** 18
	ans = min(ans, min_cost[0])
	for v in range(1, n):
		(d, i, j) = id_to_string[v]
		if d == 0:
			substring = string[i][:j]
		else:
			substring = string[i][-j:]
		if substring == substring[::-1]:
			ans = min(ans, min_cost[v])
	if ans == 10 ** 18:
		print(-1)
	else:
		print(ans)
main()


from heapq import heapify, heappop, heappush

def rolling(s):
	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))
				elif 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))
				elif 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 collections import deque

def is_palindrome(S):
	d = deque(S)
	while d:
		if len(d) <= 1:
			return True
		if d[0] != d[-1]:
			return False
		d.popleft()
		d.pop()
	return True

def union(S1, S2):
	l1 = len(S1)
	l2 = len(S2)
	for i in range(min(l1, l2)):
		if S1[i] != S2[-i - 1]:
			return (-1, '')
	if abs(l1 - l2) <= 1:
		return (2, '')
	if l1 > l2:
		return (0, S1[l2:])
	else:
		return (1, S2[:l2 - l1])
N = int(input())
S = []
C = []
d = deque()
dic = {}
ans = 10 ** 18
for i in range(N):
	(Si, Ci) = input().split()
	Ci = int(Ci)
	S.append(Si)
	C.append(Ci)
	if is_palindrome(Si):
		ans = min(ans, Ci)
	else:
		d.append((Ci, Si, 0))
		d.append((Ci, Si, 1))
		dic[Si, 0] = Ci
		dic[Si, 1] = Ci
while d:
	(cost, string, order) = d.popleft()
	for i in range(N):
		if order == 0:
			(x, y) = union(string, S[i])
		else:
			(x, y) = union(S[i], string)
		if x == -1:
			continue
		if is_palindrome(y):
			ans = min(ans, cost + C[i])
		elif (y, x) in dic.keys():
			if dic[y, x] > cost + C[i]:
				d.append((cost + C[i], y, x))
				dic[y, x] = cost + C[i]
		else:
			d.append((cost + C[i], y, x))
			dic[y, x] = cost + C[i]
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


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]
if ans != float('inf'):
	print(ans)
else:
	print(-1)