Problem:


Score : 600 points

Problem 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.

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 1

3
ba 3
abc 4
cbaa 5

Sample Output 1

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.

Sample Input 2

2
abcab 5
cba 3

Sample Output 2

11

We can choose abcab once and cba twice, then concatenate them in the order abcab, cba, cba to make a palindrome for a cost of 11.

Sample Input 3

4
ab 5
cba 3
a 12
ab 10

Sample Output 3

8

We can choose a once, which is already a palindrome, but it is cheaper to concatenate ab and cba.

Sample Input 4

2
abc 1
ab 2

Sample Output 4

-1

We cannot make a palindrome, so we should print -1.



Sample input:
3
ba 3
abc 4
cbaa 5


Sample output:
7

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

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

def palindrome(l, r):
    if len(l+r) > 1 and 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
        while queue:
            #print(queue)
            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)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
N=int(input())
X=[list(input().split()) for i in range(N)]
for i in range(N):
  X[i][1]=int(X[i][1])
V1=set()
V2=set()
for i in range(N):
  for j in range(len(X[i][0])):
    V1.add(X[i][0][:j+1])
    V2.add(X[i][0][:j+1])
    V2.add(X[i][0][-j-1:])
    V1.add(X[i][0][-j-1:])
V1=list(V1)
V2=list(V2)
D1=dict()
D2=dict()
for i in range(len(V1)):
  D1[V1[i]]=i
for i in range(len(V2)):
  D2[V2[i]]=len(V1)+i
S=len(V1)+len(V2)+1
G=[[] for i in range(S)]
D=[0]*S
for i in range(len(V1)):
  if len(V1[i])==1:
    G[i].append((S-1,0))
  for j in range(N):
    if len(V1[i])>len(X[j][0]):
      if V1[i][:len(X[j][0])]==X[j][0][::-1]:
        G[i].append((D1[V1[i][len(X[j][0]):]],X[j][1]))
    elif len(V1[i])==len(X[j][0]):
      if V1[i]==X[j][0][::-1]:
        G[i].append((S-1,X[j][1]))
    else:
      if X[j][0][::-1][:len(V1[i])]==V1[i]:
        if D2.get(X[j][0][len(V1[i]):][::-1],-1)!=-1:
          G[i].append((D2[X[j][0][len(V1[i]):][::-1]],X[j][1]))
for i in range(len(V2)):
  if len(V2[i])==1:
    G[i+len(V1)].append((S-1,0))
  for j in range(N):
    if len(V2[i])>len(X[j][0]):
      if V2[i][:len(X[j][0])]==X[j][0][::-1]:
        G[i+len(V1)].append((D2[V2[i][len(X[j][0]):]],X[j][1]))
    elif len(V2[i])==len(X[j][0]):
      if V2[i]==X[j][0][::-1]:
        G[i+len(V1)].append((S-1,X[j][1]))
    else:
      if X[j][0][::-1][:len(V2[i])]==V2[i]:
        if D1.get(X[j][0][len(V2[i]):][::-1],-1)!=-1:
          G[i+len(V1)].append((D1[X[j][0][len(V2[i]):][::-1]],X[j][1]))
Z=[[] for i in range(len(V1)+len(V2)+1)]
for i in range(len(G)):
  for j in range(len(G[i])):
    Z[G[i][j][0]].append((i,G[i][j][1]))
INF=10**18
from heapq import *
from copy import *
G=deepcopy(Z)
def ijk(s):
  global D,INF,G
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(S-1)
P=INF

for i in range(N):
  P=min(P,D[D1[X[i][0]]]+X[i][1])
if P!=INF:
  print(P)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
INF = 10**12
N = int(input())
D = dict()
for _ in range(N):
    s, c = input().split()
    if s in 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 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 D.keys():
            # reversed s is included in the end of t
            if t[::-1].find(s) == 0:
                use[t] += 1
                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 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 D.keys():
        use = {s: 0 for s in D.keys()}
        use[s] = 1
        ans = find_candidate(ans, use, s, True)
    return ans if ans < INF else -1

if __name__ == "__main__":
    print(solve())

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**18)
from collections import defaultdict
inf = 10**18

def main():
    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_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    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_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    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_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S = []
    C = []
    for i in range(N):
        s,c = input().split()
        S.append(s)
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S[i][::-1]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S = []
    C = []
    for i in range(N):
        s,c = input().split()
        S.append(s)
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S[i][::-1]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
inf = 10**18
N = int(input())
S = []
C = []
for i in range(N):
    s,c = input().split()
    S.append(s)
    C.append(int(c))
    
d_l = defaultdict(lambda:inf)
def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    if d_l[s1] != inf:
        return d_l[s1]
    for i in range(N):
        s2 = S[i][::-1]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    d_l[s1] = res
    return res

d_r = defaultdict(lambda:inf)
def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    if d_r[s2] != inf:
        return d_r[s2]
    for i in range(N):
        s1 = S[i]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    d_r[s2] = res
    return res

ans = inf
for i in range(N):
    ans = min(ans,left(S[i])+C[i])

if ans == inf:
    ans = -1

print(ans)

Submission status: Runtime Error

Solution code:
inf = 10**18
N = int(input())
S = []
C = []
for i in range(N):
    s,c = input().split()
    S.append(s)
    C.append(int(c))

def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    for i in range(N):
        s2 = S[i][::-1]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    for i in range(N):
        s1 = S[i]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

ans = inf
for i in range(N):
    ans = min(ans,left(S[i])+C[i])

if ans == inf:
    ans = -1

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
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)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
base = 10**20
@lru_cache(maxsize=None)
def decode(x):
  a = x%base
  x //= base
  b = x%base
  x //= base
  c = x%base
  x //= base
  d = x%base
  return [a,b,c,d]

R,C,K = IL()
data = [[0 for i in range(C)] for j in range(R)]
for _ in range(K):
  j,i,v = IL()
  data[j-1][i-1] = v

dp = [[0 for i in range(C+1)] for j in range(R+1)]
for j in range(R):
  for i in range(C):
    v = data[j][i] 
    if v == 0:
      dp[j+1][i+1] += max(decode(dp[j+1][i])[0],max(decode(dp[j][i+1])))
      dp[j+1][i+1] += max(decode(dp[j+1][i])[1],max(decode(dp[j][i+1])))*base
      dp[j+1][i+1] += max(decode(dp[j+1][i])[2],max(decode(dp[j][i+1])))*base**2
      dp[j+1][i+1] += max(decode(dp[j+1][i])[3],max(decode(dp[j][i+1])))*base**3
    else:
      dp[j+1][i+1] += max(decode(dp[j+1][i])[0],max(decode(dp[j][i+1])))
      dp[j+1][i+1] += max(decode(dp[j+1][i])[1],decode(dp[j+1][i])[0]+v,max(decode(dp[j][i+1]))+v)*base
      dp[j+1][i+1] += max(decode(dp[j+1][i])[2],decode(dp[j+1][i])[1]+v,max(decode(dp[j][i+1]))+v)*base**2
      dp[j+1][i+1] += max(decode(dp[j+1][i])[3],decode(dp[j+1][i])[2]+v,max(decode(dp[j][i+1]))+v)*base**3
print(max(decode(dp[-1][-1])))

Submission status: Runtime Error

Solution code:
/* #region header */
#ifdef LOCAL
    #include "/Users/takakurashokichi/Desktop/atcoder/cxx-prettyprint-master/prettyprint.hpp"
    #define debug(x) cout << x << endl
#else
    #define debug(...) 42
#endif

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//types
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
typedef pair < ll , ll > Pl;        
typedef pair < int, int > Pi;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vc;
template< typename T >
using mat = vector< vector< T > >;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef vector<vector<char>> vvc;

template< int mod >
struct modint {
    int x;

    modint() : x(0) {}

    modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    modint &operator+=(const modint &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    modint &operator-=(const modint &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    modint &operator*=(const modint &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    modint &operator/=(const modint &p) {
        *this *= p.inverse();
        return *this;
    }

    modint operator-() const { return modint(-x); }

    modint operator+(const modint &p) const { return modint(*this) += p; }

    modint operator-(const modint &p) const { return modint(*this) -= p; }

    modint operator*(const modint &p) const { return modint(*this) *= p; }

    modint operator/(const modint &p) const { return modint(*this) /= p; }

    bool operator==(const modint &p) const { return x == p.x; }

    bool operator!=(const modint &p) const { return x != p.x; }

    modint inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
        t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
        }
        return modint(u);
    }

    modint pow(int64_t n) const {
        modint ret(1), mul(x);
        while(n > 0) {
        if(n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const modint &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, modint &a) {
        int64_t t;
        is >> t;
        a = modint< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};
//abreviations
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep_(i, a_, b_, a, b, ...) for (ll i = (a), max_i = (b); i < max_i; i++)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define rrep_(i, a_, b_, a, b, ...) for (ll i = (b-1), min_i = (a); i >= min_i; i--)
#define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define SZ(x) ((int)(x).size())
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define mp make_pair
#define print(x) cout << x << endl
#define vprint(x) rep(i, x.size())cout << x[i] << ' '; cout << endl
#define vsum(x) accumulate(all(x), 0LL)
#define vmax(a) *max_element(all(a))
#define vmin(a) *min_element(all(a))
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
//functions
//gcd(0, x) fails.
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template< typename T >
T mypow(T x, ll n) {
    T ret = 1;
    while(n > 0) {
        if(n & 1) (ret *= x);
        (x *= x);
        n >>= 1;
    }
    return ret;
}
ll modpow(ll x, ll n, const ll mod) {
    ll ret = 1;
    while(n > 0) {
        if(n & 1) (ret *= x);
        (x *= x);
        n >>= 1;
        x%=mod;
        ret%=mod;
    }
    return ret;
}
template< typename T >
uint64_t my_rand(void) {
    static uint64_t x = 88172645463325252ULL;
    x = x ^ (x << 13); x = x ^ (x >> 7);
    return x = x ^ (x << 17);
}
int popcnt(ull x) { return __builtin_popcountll(x); } 
//graph template
template< typename T >
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    bool operator<(const edge<T> &r) const { return cost < r.cost; }
    
    operator int() const { return to; }
};
template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
struct Timer { 
    clock_t start_time; 
    void start() {
        start_time = clock(); 
    }
    int lap() { 
        //return x ms.
        return (clock()-start_time)*1000 / CLOCKS_PER_SEC; 
    }
};
/* #endregion*/
//constant
#define inf 1000000005
#define INF 8000000004000000000LL
#define mod 1000000007LL
//#define endl '\n'
typedef modint<mod> mint;
const long double eps = 0.00000001;
const long double PI  = 3.141592653589793;
//library
bool C(string x){
    rep(i, x.size()/2){
        if(x[i]!=x[x.size()-i-1])return false;
    }
    return true;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    ll n; cin>>n;
    map<pair<string, bool>, ll> memo;
    vector<string> s(n), rs(n);
    vl c(n);
    rep(i, n){
        cin>>s[i]>>c[i];
        reverse(all(s[i]));
        rs[i] = s[i];
        reverse(all(s[i]));
    }

    auto dp = [&](string x, bool left, auto dp){
        if(memo[mp(x, left)]>0)return memo[mp(x, left)];
        if(C(x))return 0ll;
        memo[mp(x, left)] = INF;
        if(left){
            rep(i, n){
                if(rs[i].size()>x.size()){
                    if(rs[i].substr(0, x.size())==x)chmin(memo[mp(x, left)], dp(s[i].substr(0, s[i].size()-x.size()), false, dp)+c[i]);
                }else{
                    if(x.substr(0, rs[i].size())==rs[i])chmin(memo[mp(x, left)], dp(x.substr(s[i].size(), x.size()), true, dp)+c[i]);
                }
            }
        }else{
            reverse(all(x));
            string rx = x;
            reverse(all(x));
            rep(i, n){
                if(s[i].size()>rx.size()){
                    if(s[i].substr(0, x.size())==rx)chmin(memo[mp(x, left)], dp(s[i].substr(x.size(), s[i].size()), true, dp)+c[i]);
                }else{
                    if(rx.substr(0, s[i].size())==s[i])chmin(memo[mp(x, left)], dp(x.substr(0, x.size()-s[i].size()), false, dp)+c[i]);
                }
            }
        }
        return memo[mp(x, left)];
    };
    ll ans = INF;
    rep(i, n){
        chmin(ans, dp(s[i], true, dp)+c[i]);
    }
    print((ans==INF?-1:ans));

}

Submission status: Runtime Error

Solution code:
n=int(input())
s=[None]*n
c=[None]*n
for i in range(n):
  s_i,c_i=input().split()
  s=s_i
  c[i]=int(c_i)
score=100000000000000
for i in range(n):
  for j in range(n):
    for k in range(n):
      for l in range(n):
        s0="".join(s[i],s[j])
        s1="".join(s[i],s[k])
        s2="".join(s[i],s[l])
        s3="".join(s[i],s[j],s[k])
        s4="".join(s[i],s[k],[l])
        s5="".join(s[i],s[j],s[k],s[l])
        if s0==s0[::-1]:
          score=min(score,c[i]+c[j])
        if s1==s1[::-1]:
          score=min(score,c[i]+c[k])
        if s2==s2[::-1]:
          score=min(score,c[i]+c[l])
        if s3==s3[::-1]:
          score=min(score,c[i]+c[j]+c[k])
        if s4==s4[::-1]:
          score=min(score,c[i]+c[k]+c[l])
        if s5==s5[::-1]:
          score=min(score,c[i]+c[j]+c[k]+c[l])
if score==100000000000000:
  print(-1)
else:
  print(score)

Submission status: Runtime Error

Solution code:
def ispalindrome(s):
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            return False
    return True

def main():
    N = int(input())
    S = []
    R = []
    INF = 10**40
    for _ in range(N):
        s, cc = input().split()
        c = int(cc)
        S.append((s, c))
        R.append((s[::-1], c))
    def helper(h, t):
        if not h and not t:
            return 0
        m = INF
        if not h:
            if ispalindrome(t):
                return 0
            for s, c in S:
                if s.startswith(t):
                    k = helper(s[len(t):], '')
                    if k < 0:
                        continue
                    m = min(m, c + k)
                elif t.startswith(s):
                    k = helper('', t[len(s):])
                    if k < 0:
                        continue
                    m = min(m, c + k)
                else:
                    continue
        else:
            if ispalindrome(h):
                return 0
            for s, c in R:
                if s.startswith(h):
                    k = helper('', s[len(h):])
                    if k < 0:
                        continue
                    m = min(m, c + k)
                elif h.startswith(s):
                    k = helper(h[len(s):], '')
                    if k < 0:
                        continue
                    m = min(m, c + k)
                else:
                    continue
        if m == INF:
            return -1
        return m
    M = INF
    for s, c in S:
        k = helper(s, '')
        if k < 0:
            continue
        M = min(M, c + k)
    if M == INF:
        return -1
    return M

print(main())