Chef likes problems related to learning new languages. He only knows first N letters of English alphabet. Also he explores all M-letter words formed by the characters he knows. Define cost for a given M-letter word S, cost(S) = P1, S1+P2, S2+...+PM, SM, where Pi, j is i, jth entry of matrix P. Sort all the words by descending cost, if costs are equal, sort them lexicographically. You need to find K-th M-letter word in Chef's order.

-----Input-----
First line contains three positive integer numbers N, M and K.
Next M lines contains N integers per line, denoting the matrix P.

-----Output-----
Output in a single line K-th M-letter in Chef's order.

-----Constraints-----
- 1 ≤ N ≤ 16 
- 1 ≤ M ≤ 10 
- 1 ≤ K ≤ NM
- 0 ≤ Pi, j ≤ 109

-----Subtasks-----
- Subtask #1: (20 points) 1 ≤ K ≤ 10000
- Subtask #2: (20 points) 1 ≤ M ≤ 5
- Subtask #3: (60 points) Original constraints

-----Example-----
Input:2 5 17
7 9
13 18
10 12
4 18
3 9

Output:aaaba

Difficulty: interview

Starter code:

Solutions:
def dfs(ind,m,n,k):
 if(ind == m):
  return [""]
 else:
  temp = dfs(ind+1,m,n,k)
  ans = []
  if(len(temp)<k):
   for i in temp:
    for j in range(97,97+n):
     ans += [chr(j)+i]
  else:
   for i in temp:
    ans += ["z"+i]
 return ans
n,m,k = list(map(int,input().split()))
p = []
mr= []
for _ in range(m):
 inp = [int(x) for x in input().split()]
 mc = inp[0]
 mi = 0
 for j in range(1,n):
  if(mc<inp[j]):
   mc = inp[j]
   mi = j
 p += [inp]
 mr += [mi]
ans = dfs(0,m,n,k)
w = []
for i in ans:
 cst = 0
 s = ""
 for j in range(m):
  if(i[j]!="z"):
   s+=i[j]
   cst += p[j][ord(i[j])-97]
  else:
   s += chr(mr[j]+97)
 w += [(-cst,s)]
w.sort()
print(w[k-1][1])


def dfs(ind,m,n,k):
 if(ind == m):
  return [""]
 else:
  temp = dfs(ind+1,m,n,k)
  ans = []
  if(len(temp)<k):
   for i in temp:
    for j in range(97,97+n):
     ans += [chr(j)+i]
  else:
   for i in temp:
    ans += ["z"+i]
 return ans
n,m,k = list(map(int,input().split()))
p = []
for _ in range(m):
 inp = [int(x) for x in input().split()]
 p += [inp]
max_row = []
for i in p:
 max_row += [max(i)]
ans = dfs(0,m,n,k)
w = []
for i in ans:
 cst = 0
 for j in range(m):
  if(p[j]!="z"):
   cst += p[j][ord(i[j])-97]
  else:
   cst += max_row[j]
 w += [(-cst,i)]
w.sort()
print(w[k-1][1])


def dfs(ind,m,n):
 if(ind == m):
  return [""]
 else:
  temp = dfs(ind+1,m,n)
  ans = []
  for i in temp:
   for j in range(97,97+n):
    ans += [chr(j)+i]
 return ans
n,m,k = list(map(int,input().split()))
p = []
for _ in range(m):
 inp = [int(x) for x in input().split()]
 p += [inp]
ans = dfs(0,m,n)
w = []
for i in ans:
 cst = 0
 for j in range(m):
  cst += p[j][ord(i[j])-97]
 w += [(-cst,i)]
w.sort()
print(w[k-1][1])


n, m, k = list(map(int, input().split()))
cost = []
for i in range(m):
 cost.append(list(map(int, input().split())))

if (m<=5):
 c = 97
 s = []
 for i in range(n):
  s.append(chr(c+i))
 l = []
 def gen(x, c, ln):
  #print x, c, ln
  if (ln >= m):
   l.append((c, x))
  else:
   for i in range(n):
    xt = x+s[i]
    ct = c+cost[ln][ord(s[i])-97]
    gen(xt, ct, ln+1)
 gen('',0, 0)
 l.sort(reverse = True)
 print(l[k-1][1])