Problem:


Score : 1500 points

Problem Statement

Iroha has a sequence of N strings s_1, s_2, ..., s_N.

She will choose some (possibly all) strings from the sequence, then concatenate those strings retaining the relative order, to produce a long string.

Among all strings of length K that she can produce in this way, find the lexicographically smallest one.

Constraints

1 ≦ N ≦ 2000

1 ≦ K ≦ 10^4

For each i, 1 ≦ |s_i| ≦ K.

|s_1| + |s_2| + ... + |s_N| ≦ 10^6

For each i, s_i consists of lowercase letters.

There exists at least one string of length K that Iroha can produce.

Input

The input is given from Standard Input in the following format:

N K
s_1
s_2
:
s_N

Output

Print the lexicographically smallest string of length K that Iroha can produce.

Sample Input 1

3 7
at
coder
codar

Sample Output 1

atcodar

at and codar should be chosen.

Sample Input 2

3 7
coder
codar
at

Sample Output 2

codarat

codar and at should be chosen.

Sample Input 3

4 13
kyuri
namida
zzzzzzz
aaaaaa

Sample Output 3

namidazzzzzzz

namida and zzzzzzz should be chosen.



Sample input:
3 7
at
coder
codar


Sample output:
atcodar

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    s = []
    lens = {}
    for i in range(n):
        s.append(input())
        lens[i] = len(s[i])
    dp = [""] + ["{"] * k
    for i in range(1, k + 1):
        for index, j in enumerate(s):
            l = lens[index]
            if l <= i:
                dp[i] = sorted([dp[i], dp[i - l] + j])[0]
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().strip().split())
s=[]
kazu=[]
for i in range(N):
    s.append(input())
    kazu.append(len(s[i]))
for z in range(N):
    for x in range(N):
        if z==x:
            break
        if kazu[x]+kazu[z]==K:
            print(s[x]+s[z])
            exit()

Submission status: Wrong Answer

Solution code:
import sys

(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

possible = [ [False for x in xrange(10002)] for y in xrange(2002) ]
possible[word_num][0] = True
for i in reversed(xrange(word_num)):
    possible[i][0] = True
    for j in xrange(1, length+1):
        if len(words[i]) <= j and possible[i+1][j - len(words[i])]:
            possible[i][j] = True

result = ''
index = length
candidates = []
for i in xrange(word_num):
    if possible[i][index]:
        candidates.append({
            'pos': 0,
            'i': i,
        })

for i in xrange(1, length+1):
    chars = [ words[x['i']][x['pos']] for x in candidates ]
    chars.sort()
    ret = chars[0]
    result += ret
    index -= 1
    new_candidates = []
    new_append = new_candidates.append
    minFinished = length
    for c in candidates:
        if words[c['i']][c['pos']] != ret:
            continue
        w = words[c['i']]
        if c['pos'] < len(w) - 1:
            c['pos'] += 1
            new_append(c)
        elif c['i'] < minFinished:
            minFinished = c['i']
    for j in xrange(minFinished + 1, word_num):
        if possible[j][index]:
            new_append({
                'pos': 0,
                'i': j,
            })
    candidates = new_candidates
print result

Submission status: Wrong Answer

Solution code:
import sys

(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

possible = [ [False for x in xrange(10002)] for y in xrange(2002) ]
possible[word_num][0] = True
for i in reversed(xrange(word_num)):
    possible[i][0] = True
    for j in xrange(1, length+1):
        # if possible[i+1][j]:
        #     possible[i][j] = True
        if len(words[i]) <= j and possible[i+1][j - len(words[i])]:
            possible[i][j] = True

result = ''
index = length
candidates = []
for i in xrange(word_num):
    if possible[i][index]:
        candidates.append({
            'pos': 0,
            'i': i,
        })

for i in xrange(1, length+1):
    chars = [ words[x['i']][x['pos']] for x in candidates ]
    chars.sort()
    ret = chars[0]
    result += ret
    index -= 1
    new_candidates = []
    new_append = new_candidates.append
    minFinished = length
    for c in candidates:
        if words[c['i']][c['pos']] != ret:
            continue
        w = words[c['i']]
        if c['pos'] < len(w) - 1:
            c['pos'] += 1
            new_append(c)
        elif c['i'] < minFinished:
            minFinished = c['i']
    for j in xrange(minFinished + 1, word_num):
        if possible[j][index]:
            new_append({
                'pos': 0,
                'i': j,
            })
    candidates = new_candidates
print result

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, k = map(int, raw_input().split())
ss = []
for i in xrange(n):
    s = raw_input()
    ss.append(s)

matched = '{'
for i in xrange(1, len(ss)):
    for mystr in combinations(ss, i):
        mystr = ''.join(mystr)
        if len(mystr)==k:
            matched = min(matched, mystr)

print matched

Submission status: Wrong Answer

Solution code:
(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

cache = {}
def get_min_word(current, max_index, rest_length):
    key = '{}:{}'.format(max_index, rest_length)
    if key in cache:
        print 'use_cache'
        return cache[key]
    # print current, max_index, rest_length
    last = words[max_index]
    use_last = 'z' * rest_length + current
    if max_index == 0:
        if len(last) == rest_length:
            use_last = last + current
        return use_last
    if len(last) <= rest_length:
        new_current = last + current
        new_rest_length = rest_length-len(last)
        # print 'call'
        if new_rest_length == 0:
            use_last = new_current
        else:
            use_last = get_min_word(new_current, max_index-1, new_rest_length)
    # print 'call'
    not_use_last = get_min_word(current, max_index-1, rest_length)
    l = [use_last, not_use_last]
    l.sort()
    # print l
    cache[key] = l[0]
    return l[0]

min_word = get_min_word('', word_num - 1, length)
print min_word

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]
Kp1 = K+1
ss = [input() for _ in range(N)]
ds = ["~" * n for n in range(Kp1)]
for s in ss:
    len_s = len(s)
    for i in range(Kp1-len_s):
        t = ds[i] + s
        if t < ds[i+len_s]:
            ds[i+len_s] = t
print(ds[K])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s.split(" ")
N = int(s[0])
K = int(s[1])
sss = [None] * N
for index in range(0, N):
  s = input()
  sss[index] = s
s = sss

dp = [[None] * K for _ in range(0, N)]

dp[0][len(s[0])-1] = s[0]

for n in range(1, N):
  length = len(s[n])
  dp[n][length-1] = s[n] if dp[n-1][length-1] == None else (s[n] if s[n] <= dp[n-1][length-1] else dp[n-1][length-1])
  for k in range(0, K):
    length = k + 1
    if length == len(s[n]):
      continue
    
    dp[n][k] = dp[n-1][k]
    if length - len(s[n]) - 1 >= 0 and dp[n-1][length-len(s[n])-1] != None:
      candidate = dp[n-1][length-len(s[n])-1] + s[n]
      dp[n][k] = candidate if dp[n][k] == None or candidate <= dp[n][k] else dp[n-1][k]

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k = map(int,readline().split())
ns = read().split()

"""
compare = list(sorted((si*(k//len(si)+1),i) for i,si in enumerate(s)))

order = [0]*n
for j,(_,i) in enumerate(compare):
    order[i] = j

ns = [""]*n
for i in range(n):
    ns[order[i]] = s[i]
"""


dp = ["{"]*(1+k)
dp[0]=""

for si in ns:
    l = len(si)
    for i in range(k-l,-1,-1):
        if dp[i] != "{":
            x = "".join([dp[i],si])
            if x < dp[i+l]: dp[i+l] = x

    #print(dp)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    S = []
    L = []
    for i in range(N):
        s = input()
        S.append(s)
        L.append(len(s))
    
    dp = [["z"*(K+1) for j in range(K+1)] for i in range(N+1)]
    import copy

    for i in range(N+1):
        dp[i][0] = ""
    for i in range(1,N+1):
        for j in range(1,K+1):
            if j - L[i-1] >= 0:
                dp[i][j] = min(dp[i-1][j], "".join([dp[i-1][j - L[i-1]],S[i-1]]))
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[N][K])
    #print(dp[N][2])
    #print(dp)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    S = []
    for i in range(N):
        s = input()
        S.append(s)
    
    dp = [["z"*(K+1) for j in range(K+1)] for i in range(N+1)]
    import copy

    for i in range(N+1):
        dp[i][0] = ""
    for i in range(1,N+1):
        for j in range(1,K+1):
            if j - len(S[i-1]) >= 0:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j - len(S[i-1])] + S[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[N][K])
    #print(dp[N][2])
    #print(dp)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    S = []
    for i in range(N):
        s = input()
        S.append(s)
    
    dp = [["z"*(K+1) for j in range(K+1)] for i in range(N+1)]
    import copy

    for i in range(N+1):
        dp[i][0] = ""
    for i in range(1,N+1):
        for j in range(1,K+1):
            if j - len(S[i-1]) >= 0:
                dp[i][j] = min(dp[i][j],dp[i-1][j], dp[i-1][j - len(S[i-1])] + S[i-1])
            else:
                dp[i][j] = min(dp[i][j],dp[i-1][j])
    print(dp[N][K])
    #print(dp[N][2])
    #print(dp)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = SR(n)
dp = ['{' * l for l in range(k+1)]


for i in range(n):
    for j in range(k, len(L[i]) - 1, -1):
        dp[j] = min(dp[j-len(L[i])] + L[i], dp[j])



print(dp[k])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = SR(n)
dp = ['{' * l for l in range(k+1)]


for i in range(n):
    for j in range(k, len(L[i]) - 1, -1):
        dp[j] = min(dp[j-len(L[i])] + L[i], dp[j])



print(dp[k])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    s = []
    dp = [""] + ["{"] * k
    for _ in range(n):
        s.append(input())
    for i in s:
        l = len(i)
        for j in range(k, l - 1, -1):
            dp[j] = sorted([dp[j], dp[j - l] + i])[0]
    print(dp[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(2020)


def make_best(s, best, path):
    candidate = ''.join([s[i] for i in path])
    if best is None or candidate < best:
        return candidate
    return best


def dfs(n, k, s, l, dp, i, path, t, best):

    path.append(i)
    t += l[i]
    if t == k:
        best = make_best(s, best, path)
        path.pop()
        return best
    elif k < t:
        path.pop()
        return best
    lk = k - t
    for j in range(i + 1, n):
        if dp[j][lk]:
            best = dfs(n, k, s, l, dp, j, path, t, best)
    path.pop()
    return best


def solve(n, k, s):

    l = [len(si) for si in s]

    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[n][0] = 1
    for i in range(n - 1, -1, -1):
        li = l[i]
        lk = k - li
        for j in range(k + 1):
            if dp[i + 1][j]:
                dp[i][j] = 1
                if j <= lk:
                    dp[i][j + li] = 1

    order = [i for i in range(n)]
    order.sort(key = lambda i: s[i])

    order2 = []
    i = 0
    while i < n:
        j = order[i]
        a = [j]
        order2.append(a)
        sj = s[j]
        lj = l[j]
        ni = i + 1
        while ni < n:
            nj = order[ni]
            if lj <= l[nj]:
                snj = s[nj]
                if snj[:lj] == sj:
                    a.append(nj)
                    ni += 1
                else:
                    break
            else:
                break
        a.sort(reverse = True)
        i = ni

    best = None
    for a in order2:
        for i in a:
            if dp[i][k]:
                path = []
                best = dfs(n, k, s, l, dp, i, path, 0, best)
        if best is not None:
            break

    return best


def main():
    n, k = input().split()
    n = int(n)
    k = int(k)
    s = []
    for _ in range(n):
        si = input()
        s.append(si)

    print(solve(n, k, s))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(2020)


def make_best(s, best, path):
    candidate = ''.join([s[i] for i in path])
    if best is None or candidate < best:
        return candidate
    return best


def dfs(n, k, s, l, i, path, t, best):

    path.append(i)
    t += l[i]
    if t == k:
        best = make_best(s, best, path)
        path.pop()
        return best
    elif k < t:
        path.pop()
        return best
    for j in range(i + 1, n):
        best = dfs(n, k, s, l, j, path, t, best)
    path.pop()
    return best


def solve(n, k, s):

    l = [len(si) for si in s]

    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[n][0] = 1
    for i in range(n - 1, -1, -1):
        li = l[i]
        lk = k - li
        for j in range(k + 1):
            if dp[i + 1][j]:
                dp[i][j] = 1
                if j <= lk:
                    dp[i][j + li] = 1

    order = [i for i in range(n)]
    order.sort(key = lambda i: s[i])

    order2 = []
    i = 0
    while i < n:
        j = order[i]
        a = [j]
        order2.append(a)
        sj = s[j]
        lj = l[j]
        ni = i + 1
        while ni < n:
            nj = order[ni]
            if lj <= l[nj]:
                snj = s[nj]
                if snj[:lj] == sj:
                    a.append(nj)
                    ni += 1
                else:
                    break
            else:
                break
        a.sort(reverse = True)
        i = ni

    best = None
    for a in order2:
        for i in a:
            if dp[i][k - l[i]]:
                path = []
                best = dfs(n, k, s, l, i, path, 0, best)
        if best is not None:
            break

    return best


def main():
    n, k = input().split()
    n = int(n)
    k = int(k)
    s = []
    for _ in range(n):
        si = input()
        s.append(si)

    print(solve(n, k, s))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

possible2 = [ False for x in xrange(length+2) ]
possible2[0] = True
possible = [ [False for x in xrange(length+2)] for y in xrange(word_num+2) ]
possible[word_num][0] = True
for i in reversed(xrange(word_num)):
    possible[i][0] = True
    for j in reversed(xrange(1, length+1)):
        if len(words[i]) <= j and possible2[j - len(words[i])]:
            # print (i, j)
            possible[i][j] = True
            possible2[j] = True

result = ''
index = length
positions = []
pos_append = positions.append
indexes = []
ind_append = indexes.append
for i in xrange(word_num):
    if possible[i][index]:
        pos_append(0)
        ind_append(i)

# print positions, indexes

for i in xrange(1, length+1):
    chars = [ words[indexes[x]][positions[x]] for x in xrange(len(positions)) ]
    ret = min(chars)
    new_positions = []
    np_append = new_positions.append
    new_indexes = []
    ni_append = new_indexes.append
    minFinished = length
    if len(positions) == 1:
        pos = positions[0]
        w = words[indexes[0]]
        sub = w[pos:len(w)]
        result += sub
        index -= len(sub)
        minFinished = indexes[0]
        # print result, chars, index, minFinished
        if index == 0:
            break
    else:
        result += ret
        # print result, chars, index, minFinished
        index -= 1
        for j in xrange(len(positions)):
            ind = indexes[j]
            pos = positions[j]
            ww = words[ind]
            if ww[pos] != ret:
                continue
            if pos < len(ww) - 1:
                np_append(pos+1)
                ni_append(ind)
            elif ind < minFinished:
                minFinished = ind
    for j in xrange(minFinished + 1, word_num):
        if possible[j][index]:
            np_append(0)
            ni_append(j)
    positions = new_positions
    indexes = new_indexes
print result

Submission status: Time Limit Exceeded

Solution code:
import sys

(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

possible2 = [ False for x in xrange(length+2) ]
possible2[0] = True
possible = [ [False for x in xrange(length+2)] for y in xrange(word_num+2) ]
possible[word_num][0] = True
for i in reversed(xrange(word_num)):
    possible[i][0] = True
    for j in reversed(xrange(1, length+1)):
        if len(words[i]) <= j and possible2[j - len(words[i])]:
            # print (i, j)
            possible[i][j] = True
            possible2[j] = True

result = ''
index = length
candidates = []
for i in xrange(word_num):
    if possible[i][index]:
        candidates.append({
            'pos': 0,
            'i': i,
        })

for i in xrange(1, length+1):
    chars = [ words[x['i']][x['pos']] for x in candidates ]
    ret = min(chars)
    new_candidates = []
    new_append = new_candidates.append
    minFinished = length
    if len(candidates) == 1:
        x = candidates[0]
        w = words[x['i']]
        sub = w[x['pos']:len(w)]
        result += sub
        index -= len(sub)
        minFinished = x['i']
        # print result, chars, index, minFinished
        if index == 0:
            break
    else:
        result += ret
        # print result, chars, index, minFinished
        index -= 1
        for c in candidates:
            if words[c['i']][c['pos']] != ret:
                continue
            ww = words[c['i']]
            if c['pos'] < len(ww) - 1:
                c['pos'] += 1
                new_append(c)
            elif c['i'] < minFinished:
                minFinished = c['i']
    for j in xrange(minFinished + 1, word_num):
        if possible[j][index]:
            new_append({
                'pos': 0,
                'i': j,
            })
    candidates = new_candidates
print result

Submission status: Time Limit Exceeded

Solution code:
import sys

(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

possible2 = [ False for x in xrange(length+2) ]
possible2[0] = True
possible = [ [False for x in xrange(length+2)] for y in xrange(word_num+2) ]
possible[word_num][0] = True
for i in reversed(xrange(word_num)):
    possible[i][0] = True
    for j in reversed(xrange(1, length+1)):
        if len(words[i]) <= j and possible2[j - len(words[i])]:
            # print (i, j)
            possible[i][j] = True
            possible2[j] = True

result = ''
index = length
candidates = []
for i in xrange(word_num):
    if possible[i][index]:
        candidates.append({
            'pos': 0,
            'i': i,
        })

for i in xrange(1, length+1):
    chars = [ words[x['i']][x['pos']] for x in candidates ]
    ret = min(chars)
    result += ret
    # print result, chars
    index -= 1
    new_candidates = []
    new_append = new_candidates.append
    minFinished = length
    for c in candidates:
        if words[c['i']][c['pos']] != ret:
            continue
        w = words[c['i']]
        if c['pos'] < len(w) - 1:
            c['pos'] += 1
            new_append(c)
        elif c['i'] < minFinished:
            minFinished = c['i']
    for j in xrange(minFinished + 1, word_num):
        if possible[j][index]:
            new_append({
                'pos': 0,
                'i': j,
            })
    candidates = new_candidates
print result

Submission status: Runtime Error

Solution code:
import itertools
n,k=map(int,input().strip().split())
s=[input() for i in range(n)]
let=itertools.combinations
for i in range(1,n+1):
    ss=list(let(s,i))
    for x in range(n):
        a=len(''.join(ss[x]))
        if a==k:
            print(''.join(ss[x]))
            exit()

Submission status: Runtime Error

Solution code:
import itertools
n,k=map(int,input().strip().split())
s=[input() for i in range(n)]
let=itertools.combinations
for i in range(1,n+1):
    ss=list(let(s,i))
    for z in range(n):
        a=''.join(ss[z])
        if len(a)==k:
            print(a)
            exit()

Submission status: Runtime Error

Solution code:
(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

cache = {}
def get_min_word(max_index, rest_length):
    key = '{}:{}'.format(max_index, rest_length)
    if key in cache:
        # print 'use_cache', key, cache[key]
        return cache[key]
    # print current, max_index, rest_length
    last = words[max_index]
    use_last = 'z' * rest_length
    if max_index == 0:
        if len(last) == rest_length:
            use_last = last
        return use_last
    if len(last) <= rest_length:
        new_rest_length = rest_length-len(last)
        # print 'call'
        if new_rest_length == 0:
            use_last = last
        else:
            use_last = get_min_word(max_index-1, new_rest_length) + last
    # print 'call'
    not_use_last = get_min_word(max_index-1, rest_length)
    l = [use_last, not_use_last]
    l.sort()
    # print l
    cache[key] = l[0]
    return l[0]

min_word = get_min_word(word_num - 1, length)
print min_word

Submission status: Runtime Error

Solution code:
(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

cache = {}
def get_min_word(current, max_index, rest_length):
    key = '{}:{}:{}'.format(current, max_index, rest_length)
    if key in cache:
        # print 'use_cache', key, cache[key]
        return cache[key]
    # print current, max_index, rest_length
    last = words[max_index]
    use_last = 'z' * rest_length + current
    if max_index == 0:
        if len(last) == rest_length:
            use_last = last + current
        return use_last
    if len(last) <= rest_length:
        new_current = last + current
        new_rest_length = rest_length-len(last)
        # print 'call'
        if new_rest_length == 0:
            use_last = new_current
        else:
            use_last = get_min_word(new_current, max_index-1, new_rest_length)
    # print 'call'
    not_use_last = get_min_word(current, max_index-1, rest_length)
    l = [use_last, not_use_last]
    l.sort()
    # print l
    cache[key] = l[0]
    return l[0]

min_word = get_min_word('', word_num - 1, length)
print min_word

Submission status: Runtime Error

Solution code:
(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

cache = {}
def get_min_word(current, max_index, rest_length):
    key = '{}:{}'.format(max_index, rest_length)
    if key in cache:
        # print 'use_cache'
        return cache[key]
    # print current, max_index, rest_length
    last = words[max_index]
    use_last = 'z' * rest_length + current
    if max_index == 0:
        if len(last) == rest_length:
            use_last = last + current
        return use_last
    if len(last) <= rest_length:
        new_current = last + current
        new_rest_length = rest_length-len(last)
        # print 'call'
        if new_rest_length == 0:
            use_last = new_current
        else:
            use_last = get_min_word(new_current, max_index-1, new_rest_length)
    # print 'call'
    not_use_last = get_min_word(current, max_index-1, rest_length)
    l = [use_last, not_use_last]
    l.sort()
    # print l
    cache[key] = l[0]
    return l[0]

min_word = get_min_word('', word_num - 1, length)
print min_word

Submission status: Runtime Error

Solution code:
(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

def get_min_word(current, max_index, rest_length):
    # print current, max_index, rest_length
    last = words[max_index]
    use_last = 'z' * rest_length + current
    if max_index == 0:
        if len(last) == rest_length:
            use_last = last + current
        return use_last
    if len(last) <= rest_length:
        new_current = last + current
        new_rest_length = rest_length-len(last)
        # print 'call'
        if new_rest_length == 0:
            use_last = new_current
        else:
            use_last = get_min_word(new_current, max_index-1, new_rest_length)
    # print 'call'
    not_use_last = get_min_word(current, max_index-1, rest_length)
    l = [use_last, not_use_last]
    l.sort()
    # print l
    return l[0]

min_word = get_min_word('', word_num - 1, length)
print min_word

Submission status: Runtime Error

Solution code:
(word_num, length) = tuple([ int(x) for x in raw_input().split() ])
words = [ raw_input() for _ in xrange(word_num) ]

def get_min_word(current, max_index, rest_length):
    # print current, max_index, rest_length
    last = words[max_index]
    use_last = 'z' * rest_length + current
    if max_index == 0:
        if len(last) == rest_length:
            use_last = last + current
        return use_last
    if len(last) <= rest_length:
        new_current = last + current
        # print 'call'
        use_last = get_min_word(new_current, max_index-1, rest_length-len(last))
    # print 'call'
    not_use_last = get_min_word(current, max_index-1, rest_length)
    l = [use_last, not_use_last]
    l.sort()
    # print l
    return l[0]

min_word = get_min_word('', word_num - 1, length)
print min_word