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

Submission attempts (in order):
# 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 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:
            
            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()

# 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 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[::-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
    cache = set()
    for s,c in SC:
        queue = []
        left = (s, c)
        right = ('', 0)
        heappush(queue, (c, (left, right)))
        done = False

        while queue:
            
            cost, (l, r) = heappop(queue)
            if (l[0], r[0]) in cache: continue
            cache.add((l[0], r[0]))
            if palindrome(l[0], r[0]):
                done = True
                #print(l, r)
                cache.remove((l[0], r[0]))
                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()

Verdicts: Runtime Error

Accepted