Problem:
 Score : 300 points    Problem Takahashi, who is a novice in competitive programming, wants to learn M algorithms.
Initially, his understanding level of each of the M algorithms is 0 .  Takahashi is visiting a bookstore, where he finds N books on algorithms.
The i -th book ( 1\leq i\leq N ) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j -th algorithm will increase by A_{i,j} for each j ( 1\leq j\leq M ).
There is no other way to increase the understanding levels of the algorithms.  Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.      Constraints  All values in input are integers.  1\leq N, M\leq 12  1\leq X\leq 10^5  1\leq C_i \leq 10^5  0\leq A_{i, j} \leq 10^5         Input Input is given from Standard Input in the following format:  N  M  X  C_1  A_{1,1}  A_{1,2}  \cdots  A_{1,M}  C_2  A_{2,1}  A_{2,2}  \cdots  A_{2,M}  \vdots  C_N  A_{N,1}  A_{N,2}  \cdots  A_{N,M}       Output If the objective is not achievable, print -1 ; otherwise, print the minimum amount of money needed to achieve it.        Sample Input 1 3 3 10
60 2 2 4
70 8 7 9
50 2 3 9      Sample Output 1 120  Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.       Sample Input 2 3 3 10
100 3 1 4
100 1 5 9
100 2 6 5      Sample Output 2 -1  Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.       Sample Input 3 8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2      Sample Output 3 1067

Solution (Python):
import sys
import numpy as np
from itertools import *
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N,M,X= LI()
R = [list(map(int,input().split())) for i in range(N)]
S = [0]

R.sort(key=lambda x: x[0])
i = 1
count = 0
flag = 1
ans = 9999999
while flag:
    temp = list(combinations(R, i))
    
    for q in range(0,len(temp)):
        temp2 = list(np.sum(temp[q], axis=0))
        
        n = sum(temp2[x]>=X for x in range(1,len(temp2)))
        if n == M:
            ans = min(ans,temp2[0])
    i += 1
    if i>N:
        flag = 0
if ans == 9999999:
    ans = -1
print(ans)

Solution (Python):
from itertools import product
import numpy as np

N, M, X = map(int, input().split())
p = list(product([0, 1], repeat=N))
p = np.array(p).astype(bool)


C = []
A = []

for i in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
A = np.array(A)
C = np.array(C)


INF = 10 ** 18
ans = INF

for i in range(len(p)):
    
    B = A[p[i]]
    B = np.sum(B, axis=0)
    
    if np.all(B >= X):
        ans = min(ans, C[p[i]].sum())
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
n ,m,x = map(int,input().split())
books = []
cost = 2000000000
for i in range(n):
  books.append(list(map(int,input().split())))

for i in range(1,2**n):
  bag = []
  total = 0
  value = [0]*m
  for j in range(n):
    if (i >> j) & 1:
      bag.append(books[j])
      total += books[j][0]
      for k in range(m):
        value[k] += books[j][k+1]
  if(all([e >=x for e in value])):
    cost = min(cost,total)
    
if(cost == 2000000000):
  print(-1)
else:
  print(cost)

Solution (Python):
import copy


def comall(depth,n,x,a,usum,vsum):
  allok = True
  for i in range(1,len(usum)):
    
    if usum[i] < x:
      allok = False
      break
  
  if allok:
    
    return vsum
  else:
    
    if depth >= n:
      return 10000000
    else:
      v1 = comall(depth+1,n,x,a,copy.copy(usum),vsum)
      for i in range(1,len(usum)):
        usum[i] += a[depth][i]
      v2 = comall(depth+1,n,x,a,copy.copy(usum),vsum+a[depth][0])
      return min(v1,v2)


def main():
  nmx = input().split()
  n = int(nmx[0])
  m = int(nmx[1])
  x = int(nmx[2])

  c = []
  for i in range(n):
    cn = list(map(lambda x:int(x), input().split() ))
    c.append(cn)
    
  ans = comall(0,n,x,c,[0]*(m+1),0)
  if ans == 10000000:
    print(-1)
  else:
    print(ans)
    
main()

Solution (Python):
import itertools
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

mn = 10**18
l = [i for i in range(n)]
for y in range(1, n+1):
    for v in itertools.combinations(l, y):
        tm = [0]*m
        k = 0
        for i in v:
            k += a[i][0]
            for j in range(1, m+1):
                tm[j-1] += a[i][j]
        flag = True
        for i in range(m):
            if tm[i] < x:
                flag = False
                break
        if flag:
            mn = min(k, mn)

if mn == 10**18:
    print(-1)
else:
    print(mn)

Solution (Python):
import itertools
import numpy as np


def resolve():
    N, M, X = map(int, input().split())

    C = []
    Q = []
    for i in range(N):
        QQ = list(map(int, input().split()))
        C.append(QQ[0])
        Q.append(QQ[1:])

    C = np.array(C)
    Q = np.array(Q)
    ok = False

    NN = range(N)
    ans = np.sum(C)

    for j in range(1, N + 1):
        for jj in list(itertools.combinations(NN, j)):
            tmp_value = C[list(jj)]
            tmp_score = Q[list(jj)]
            sum_ = tmp_score.sum(axis=0)
            finish_sum_ = len(list(filter(lambda x: x >= X, sum_)))

            if finish_sum_ == M:
                ans = min(ans, tmp_value.sum())
                ok = True

    if not ok:
        print(-1)
        return

    print(ans)


resolve()

Solution (Python):
N, M, X = map(int, input().split())
A, C = [], []
for _ in range(N):
    tmp = input().split()
    C.append(int(tmp[0]))
    A.append([int(i) for i in tmp[1:]])
is_clear = False
min_cost = 10**10
for flg_number in range(2 ** N):
    flgs = format(flg_number, '0'+str(N)+'b')
    thr = [X] * M
    cost = 0
    for i in range(N):
        if flgs[i] == '1':
            cost += C[i]
            for j in range(M):
                thr[j] -= A[i][j]
    is_all_clear = True
    for j in range(M):
        if thr[j] > 0:
            is_all_clear = False
            break
    if is_all_clear:
        is_clear = True
        if min_cost > cost:
            min_cost = cost
if is_clear:
    print(min_cost)
else:
    print(-1)

Solution (Python):
import sys



n,m,x=map(int,input().split())

a=[]

s=[0]*m

money=0

for i in range(n):
  A=list(map(int,input().split()))
  a.append(A)

  money+=A[0]

  for j in range(1,m+1):
    s[j-1]+=A[j]

for i in range(m):
  if s[i]<x:
    print("-1")
    sys.exit()




buy=[0]*n

saitei=-1

for i in range(1,(2**n)+1): 
  buy=[0]*n
  t=[0]*m
  money=0
  i1=i
  for j in range(n): 
    buy[j]=(i1)%2
    i1=int((i1)/2)

    if buy[j]==1:
      money+=a[j][0]
      for k in range(1,m+1): 
        t[k-1]+=a[j][k]
  
  
  flag=True
  for r in range(m):
    if t[r]<x:
      flag=False
      break
  if flag==True:
    if saitei==-1 or saitei>money:
      saitei=money

print(saitei)

Solution (Python):
n, m, x = map(int, input().split())

c = []
a = []


def inc(l):
    if l[-1] == 0:
        l[-1] = 1
        return l
    else:
        l[-1] = 0
        return inc(l[:-1]) + [0]


def buy(a, l):
    sum_ = 0
    exps = [0] * m

    for i in range(n):
        if l[i] == 0:
            continue
        else:
            for j in range(m):
                exps[j] += a[i][j]
            sum_ += c[i]

    good = True

    for i in range(m):
        if exps[i] < x:
            good = False
            break

    return sum_, good


for i in range(n):
    line = list(map(int, input().split()))
    c.append(line[0])
    a.append(line[1:])

min_ = 99999999999999

selected = [0] * n

for i in range(2**n):
    try:
        sum_, good = buy(a, selected)

        if good and sum_ < min_:
            min_ = sum_

        selected = inc(selected)

    except:
        if min_ == 99999999999999:
            print(-1)
        else:
            print(min_)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

n,m,x = map(int,input().split())

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

res = 10**20

for p in range(1<<n):
    tmp = 0
    cnt = [0]*m
    for j in range(n):
        if (p>>j)&1 == 1:
            tmp += ca[j][0]
            for i in range(1,m+1):
                cnt[i-1] += ca[j][i]
    
    if min(cnt) >= x:
        res = min(res,tmp)
if res == 10**20:
    print(-1)
else:
    print(res)

Solution (Python):
from itertools import combinations
import numpy as np
def main():
    N, M, X = map(int, input().split())
    books = np.array([list(map(int,input().split())) for i in range(N)])
    value = select(N, M ,X, books)
    print(value)



def select(N, M, X, books):
    kouho = []
    selected = range(0, N)
    skills = books[:, 1:]
    for i in range(N, -1, -1):
        for perm in combinations(selected, i):
            selected_skills = skills[list(perm)]
            s = selected_skills.sum(axis=0)
            if len(s[s<X]) > 0:
                continue
            else:
                kouho.append(perm)
    if len(kouho) == 0:
        return -1
    value = min([sum([books[i][0] for i in k]) for k in kouho])
    return value


if __name__ == '__main__':
    perm = main()

Solution (Python):
def main():
    n, m, x = [int(e) for e in input().split()]
    CA = [[int(e) for e in input().split()] for i in range(n)]

    ans = 10 ** 9
    for i in range(1, 2 ** n):
        bs = format(i, f'0{n}b')

        cs = 0
        Sm = [0] * m
        for i in range(n):
            if bs[i] == '1':
                cs += CA[i][0]
                for mi in range(m):
                    Sm[mi] += CA[i][mi + 1]

        if all(sm >= x for sm in Sm):
            ans = min(cs, ans)

    print(-1 if ans == 10 ** 9 else ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations
n, m, x = map(int, input().split())

a = [[0 for j in range(m)] for i in range(n)]
c = [0] * n

for i in range(n):
    ca = list(map(int, input().split()))
    for j in range(m):
        c[i] = ca[0]
        a[i][j] = ca[j+1]

for i in range(m):
    s = 0
    for j in range(n):
        s += a[j][i]
    if s < x:
        print(-1)
        exit()

s = 1000000000

for i in range(1, n+1):
    for j in list(combinations(range(n), i)):
        t = [0] * m
        S = 0
        for k in range(len(j)):
            S += c[j[k]]
            for l in range(m):
                t[l] += a[j[k]][l]
        p = s
        s = min(s, S)
        for y in range(m):
            if t[y] < x:
                s = p
                break
print(s)

Solution (Python):
n,m,x = map(int,input().split())
t = []
for i in range(n):
  ti = list(map(int,input().split()))
  t.append(ti)
mn = float("inf")
flag = False
for i in range(2**n):
  cost = 0
  a =[0]*m
  j = 0
  while i > 0:
    if i%2 == 1:
      cost += t[j][0]
      for k in range(m):
        a[k] += t[j][1+k]
    i = i//2
    j += 1
  if min(a)>=x:
    flag = True
    if cost < mn:
      mn = cost
if flag:
  print(mn)
else:
  print(-1)

Solution (Python):
import sys
from itertools import product
import numpy as np
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M, X = map(int, readline().split())
    CA = list(list(map(int, readline().split())) for _ in range(N))
    CA = np.array(CA)
    target = [0] + [X]*M
    target = np.array(target)
    ans = INF
    for i in range(2**N):
        tmp = 0
        for j in range(N):
            if (i>>j)&1:
               tmp += CA[j]
        if np.all(tmp>=target):
            ans = min(ans, tmp[0])
    print(-1 if ans==INF else ans)

if __name__ == '__main__':
    main()

Solution (Python):
def combinationListRecursive(data, r):
  result = []
  _combinationListRecursive(data, r, 0, [], result)
  return result

def _combinationListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)

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

tmp = []
for i in range(1, n+1):
    c = combinationListRecursive(t, i)
    for j in c:
        cnt = [0] * (m + 1)
        for k in j:
            for l in range(m+1):
                cnt[l] += k[l]
        tmp.append(cnt)

ans = float("INF")
for i in tmp:
    ignore = False
    for j in i[1:]:
        if x > j:
            ignore = True
    if ignore:
        continue

    ans = min(ans, i[0])

if ans == float("INF"):
    ans = -1

print(ans)

Solution (Python):
import itertools

N,M,X=map(int,input().split(' '))

book=[]
skil=[0]*M
for i in range(N):
    line=list(map(int,input().split(' ')))
    book.append(line)
    skil=list(map(lambda x,y:x+y,skil,line[1:]))

min_p=12000000
for n in range(1,N+1):
    for conbo in itertools.combinations(book,n):
        conbo_book=[0]*(1+M)
        for b in list(conbo):
            conbo_book=list(map(lambda x,y:x+y,conbo_book,b))
        if len([m for m in conbo_book[1:] if m>=X])==M:
            if min_p>conbo_book[0]:
                min_p=conbo_book[0]

print(min_p) if min_p<12000000 else print("-1")

Solution (Python):
import itertools
fi = list(map(int,input().split()))
n = fi[0]
m = fi[1]
x = fi[2]
c = []
cn = []
y = 1
for k in range(n):
  cn.append(k)
for i in range(n):
  a = list(map(int,input().split()))
  c.append(a)
for j in range(m):
  wa = 0
  for s in range(n):
    wa=wa+c[s][j+1]
  if wa < x:
    y=y*0

money = []
if not y==0:
  for s in range(n+1):
    ca = list(itertools.combinations(cn, s+1))
    cb = len(ca)
    for q in range(cb):
      cwa = []
      chan = 0
      for l in range(m+1):
        cwa.append(0)
      for p in range(s+1):
        cwa = list(map(lambda x,y: x+y, c[ca[q][p]], cwa))
      for t in range(m):
        if cwa[t+1]>=x:
          chan = chan+1
        if chan ==m:
          money.append(cwa[0])
  print(min(money))
else:
  print(-1)

Solution (Python):
import itertools
n, m, x = map(int, input().split())
a = [0] * n
ans = 100000000
for i in range(n):
    a[i] = list(map(int, input().split()))
for i in range(1, n+1):
    for j in itertools.combinations(range(n), i):
        b = [0] * m
        c = 0
        for k in list(j):
            for l in range(m):
                b[l] += a[k][l+1]
            c += a[k][0]
        if sum(y >= x for y in b) == m:
            ans = min(ans, c)
if ans == 100000000:
    print(-1)
else:
    print(ans)

Solution (Python):
import numpy as np
import itertools
N,M,X=map(int,input().split())
CA=[]
D=[]

for n in range(N):
  arr=list(map(int,input().split()))
  CA.append(arr)
CA=np.array(CA)

v=list(itertools.product([0,1], repeat=N))

for v_ in v:
  SUM=np.zeros(M+1)
  for n in range(N):
    if v_[n]==1:
      SUM = SUM+CA[n]
  D.append(list(SUM))

key=[]
value=[]
  
for d in D:
  key.append(d[0])
  value.append(d[1:])
  
dict = dict(zip(key,value))
dict_sorted = sorted(dict.items(), key=lambda x:x[0])


for d in dict_sorted:
  if all([i>=X  for i in d[1]]):
    print(int(d[0]))
    exit()

print(-1)

Solution (Python):
b0=input().split()
book=int(b0[0])
pro=int(b0[1])
norma=int(b0[2])

bl=[]
for x in range(book):
  bl.append([int(y) for y in input().split()])
  
mn=-1
for x in range(2**book):
  if book>9:
    k=str(book)+"b"
  else:
    k="0"+str(book)+"b"
  x2=format(x, k)
  m=0
  exl=[0 for i in range(pro)]
  for y in range(book):
    if x2[y]=="1":
      m+=bl[y][0]
      for j in range(pro):
        exl[j]+=bl[y][j+1]
  if min(exl)>=norma and (mn==-1 or mn>m):
    mn=m

print(mn)

Solution (Python):



debug=1
def pront(*n):
    if debug==1:
        print(n)
        


base=10**9+7

def add(a,b):
    return (a+b)%base

def sub(a,b):
    return (a-b)%base

def multi(a,b):
    return (a*b)%base

def exp(a,b):
    x=1
    c=a
    d=b
    while d!=0:
        if d%2==1:
            x=multi(x,c)
        c=(c**2)%base
        d=d//2
    return x

def div(a,b):
    return(multi(a,exp(b,base-2)))


N,M,Z=map(int,input().split())

A=[list(map(int,input().split())) for i in range(N)]


X=[0 for i in range(N)]
x=float('inf')
while True:
    Y=[0 for i in range(M)]
    z=0
    for i in range(N):
        if X[i]==1:
            z+=A[i][0]
            for j in range(M):
                Y[j]+=A[i][j+1]
    for j in range(M):
        if Y[j]<Z:
            break
        if  j==M-1:
            
            if z<x:
                
                x=z
    for i in range(N):
        if X[-i-1]==0:
            X[-i-1]=1
            break
        else:
            X[-i-1]=0
    
    if X==[0 for i in range(N)]:
        break
if x==float('inf'):
    print(-1)
else:
    print(x)

Solution (Python):
n, m, x = map(int, input().split())
a = []
for i in range(n):
    b = list(map(int, input().split()))
    a.append(b)
l = []
for f in range(2**n):
    p = [0]*(m+1)
    for i in range(n):
        if (bin(f >> i)[-1] == '1'):
            for j in range(m+1):
                p[j] += a[i][j]
    if min(p[1:]) >= x:
        l.append(p[0])
if len(l) == 0:
    print('-1')
else:
    print(min(l))

Solution (Python):
import itertools
N, M, X = map(int, input().split())
book_lists = [list(map(int, input().split())) for i in range(N)]
no_skill_flg = True
for i in range(1, N+1):
    for j in itertools.combinations(book_lists,i):
        sum_list = [0 for _ in range(M+1)]
        for book_date in j:
            for k, l in enumerate(book_date):
                sum_list[k] += l
        if all([s >= X for s in sum_list[1:]]):
            no_skill_flg = False
            if 'ans' in globals():
                ans = min(ans, sum_list[0])
            else:
                ans = sum_list[0]
print(ans if not no_skill_flg else -1)

Solution (Python):
n, m, x = map(int, input().split())
master = []
ans = 10 ** 18
for i in range(n):
    b = list(map(int, input().split()))
    master.append(b)

for i in range(2 ** n):
    kau = [0 for _ in range(m + 1)]
    for j in range(n):
        if (i >> j) & 1:
            
            for k in range(m + 1):
                kau[k] += master[j][k]
    ng = 0
    for k in range(1, m + 1):
        if kau[k] < x:
            ng = 1
    if not ng:
        ans = min(ans, kau[0])
    
    
print(ans if ans != 10 ** 18 else -1)

Solution (Python):

import numpy as np

N, M, X = map(int, input().split())
A = np.zeros((N, M), dtype=np.int32)
C = np.zeros(N, dtype=np.int32)

for i in range(N):
  H = list(map(int, input().split()))
  C[i] = H[0]
  A[i,:] = H[1:M+1]

Sum = A.sum(axis=0)
price = []
if(min(Sum) < X):
  print('-1')
else:
  for i in range(2**N):
    bb = bin(i)
    B = [0]*N
    B += [int(bb[k]) for k in range(2, len(bb))]
    B = np.array([B[-N:]]).T

    pro = A*B
    s = pro.sum(axis=0)
    if(min(s) >= X):
      price.append(np.dot(C,B)[0])

  print(min(price))

Solution (Python):
N, M, X = list(map(int, input().split()))
CA = [list(map(int, input().split())) for i in range(N)]

set_list = []
for i in range(2 ** N):
    select = []
    for j in range(N):
        if ((i >> j) & 1):
            select.append(j)
    if len(select) != 0:
        set_list.append(select)
    
cost = []
for i in range(2 ** N - 1):
    cost.append(sum([CA[set_list[i][j]][0] for j in range(len(set_list[i]))]))

skill = []
for i in range(2 ** N - 1):
    tmp = [0]*M
    for j in set_list[i]:
        for k in range(M):
            tmp[k] += CA[j][k+1]
    skill.append(tmp)

pool = []
for i in range(2**N - 1):
    flag = 0
    for j in skill[i]:
        if j < X:
            flag = 1
    if flag == 0:
        pool.append(cost[i])
        

if len(pool) == 0:
	print(-1)
else:
    print(min(pool))

Solution (Python):
from itertools import combinations

N, M, X = map(int, input().split())
skill = [0] * M
N_list = []
C_sum = 0
all_list = [0] * (M+1)

res_list = 0
for i in range(N):
  list_ = list(map(int, input().split()))
  N_list.append(list_)
  all_list = [all_list[i]+list_[i] for i in range(M+1)]

result = []  
for i in range(1, N+1):
  ref = list(combinations(N_list, i))
  for j in range(len(ref)):
    sums = [0] * (M+1)
    for k in range(i):
      sums = [sums[l]+ref[j][k][l] for l in range(M+1)]
    result.append(sums)
kekka = []
for i in range(len(result)):
  if all(result[i][j]>=X for j in range(1, M+1)):
    kekka.append(result[i][0])
if kekka != []:
  print(min(kekka))
else:
  print(-1)

Solution (Python):

import itertools
import numpy as np

n,m,x = input().split(' ')
book_list = []
for i in range(int(n)):
    book_list.append([int(s) for s in input().split(' ')])
    
ok_list = []
for num in range(1,len(book_list)+1):
    for i in itertools.combinations(book_list,num):
        goukei = np.sum(np.array(i),axis=0)
        flag = True
        for j in range(1,len(goukei)):
            if goukei[j] < int(x):
                flag = False
                break
        if flag:
            ok_list.append(goukei.tolist())
            
if ok_list:
    print(sorted(ok_list)[0][0])
else:
    print(-1)

Solution (Python):
n, m, x = map(int, input().split())
c = list()
a = list()
for i in range(n):
  row_input = list(map(int, input().split()))
  c.append(row_input[0])
  a.append(row_input[1:])
inf_value = 2*sum(c)
def check_valid(completed_choice):
  jth_skill = [0]*m
  for i in range(n):
    if completed_choice[i] == 1:
      for j in range(m):
        jth_skill[j] += a[i][j]
  return all(value>=x for value in jth_skill)
def choose_next_row(partial_choice):
  if len(partial_choice) == n:
    if check_valid(partial_choice):
      return sum(include*cost for include, cost in zip(partial_choice, c))
    else:
      return inf_value
  return min(choose_next_row(partial_choice+[0]), choose_next_row(partial_choice+[1]))
ans = choose_next_row([])
if ans == inf_value:
  print(-1)
else:
  print(ans)

Solution (Python):
import itertools, numpy
n, m, x = map(int, input().split())
l = list(list(map(int, input().split())) for i in range(n))
sm = numpy.sum(l, axis=0)
ad = -1
kk = []

for k in range(n):
    com = list(itertools.combinations(l,k+1))
    sm = numpy.sum(com, axis=1)
    for i in range(len(sm)):
        kk.append(sm[i])
    
kk.sort(key=lambda z: z[0])

for i in range(len(kk)):
    if all(s >= x for s in kk[i][1:]) == True:
        ad = kk[i][0]
        break
print(ad)

Solution (Python):
from copy import copy


def recursive_bober(k, s):
    global n
    global arr
    global perm
    
    if k == n:
        perm.append(list(map(int, s.split())))
        return
    
    recursive_bober(k + 1, s)
    s += str(arr[k]) + ' '
    recursive_bober(k + 1, s)


n, m, x = map(int, input().split())
c = [0] * n
a = [[0] * m] * n
jojo = []

for i in range(n):
    cur = list(map(int, input().split()))
    c[i] = cur[0]
    for j in range(1, m + 1):
        a[i][j - 1] = cur[j]
    
    jojo.append(a[i].copy())

arr = [0] * n
for i in range(n):
    arr[i] = i

perm = []
recursive_bober(0, '')

mn = 10 ** 10
for i in perm:
    bober = [0] * m
    sum = 0
    
    for j in i:
        sum += c[j]
        for k in range(m):
            bober[k] += jojo[j][k]
    
    bad = False
    for j in bober:
        if j < x:
            bad = True
            break
    
    if not bad:
        mn = min(mn, sum)

print(mn if mn != 10 ** 10 else -1)

Solution (Python):
import itertools

def main():

    n,m,x = map(int,input().split())
    C = []
    A = []
    for i in range(n):
        array = list(map(int,input().split()))
        C.append(array[0])
        A.append(array[1:])
    cost = 10**10
    for i in range(1,n+1):
        combs = itertools.combinations(range(n), i)
        for comb in combs:
            skill = [0]*m
            cost_tmp = 0
            for e in comb:
                cost_tmp += C[e]
                for j in range(m):
                    skill[j] += A[e][j]
            for j in range(m):
                if skill[j] < x:
                    break
                if j == m-1:
                    cost = min(cost, cost_tmp)
    if cost == 10**10:
        print(-1)
        return
    print(cost)


if __name__ == '__main__':
    main()

Solution (Python):
N, M, X = [int(v) for v in input().strip().split(" ")]

C = []
A = []
for _ in range(N):
    items = [int(v) for v in input().strip().split(" ")]
    C.append(items[0])
    A.append(items[1:])


selection = []


class Solution():
    def __init__(self, N, M, X, A, C):
        self.N = N
        self.M = M
        self.X = X
        self.A = A
        self.C = C
        self.min_cost = sum(self.C) + 100


    def search(self, from_index, selection=None):
        if from_index < self.N:
            for i in range(from_index, self.N):
                s = selection + [i]
                result = self.search(from_index=i + 1, selection=s)
                if result != -1:
                    if result < self.min_cost:
                        self.min_cost = result
            this_result = self.search(from_index=self.N, selection=selection)
            if this_result != -1:
                if this_result < self.min_cost:
                    self.min_cost = this_result
            return self.min_cost
        else:
            XX = [self.X] * self.M
            for s in selection:
                for j in range(self.M):
                    XX[j] -= self.A[s][j]

            success_flag = True
            for x in XX:
                if x > 0:
                    success_flag = False
                    break

            if success_flag:
                money = 0
                for s in selection:
                    money += self.C[s]
                return money
            else:
                return -1

s = Solution(N, M, X, A, C)

result = s.search(from_index=0, selection=selection)
if result == sum(C) + 100:
    print(-1)
else:
    print(result)

Solution (Python):
import sys
n, m, x = map(int, input().split())
MAX = sys.maxsize

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

kingaku = 0
memos = [[0] * (m+2) for _ in range(n)]


def rec(i, rikaido, kingaku):
    
    
    
    
    if all([i >= x for i in rikaido]):
        return kingaku

    
    if i == n:
       return MAX

    return min(rec(i+1, rikaido, kingaku), rec(i+1, [u+t for u, t in zip(rikaido, datas[i][1:])], kingaku+datas[i][0]))


ans = rec(0, [0] * m , 0)
if ans == MAX:
    print(-1)
else:
    print(ans)

Solution (Python):
n,m,x = [int(i) for i in input().split()]
bk = []
for _ in range(n):
   bk.append([int(i) for i in input().split()])
rp = 2**n 
ans = 10000000
for i in range(rp):
   rikai = [0]*m
   mon = 0
   for j in range(n):
      if i>>j & 1:
         mon += bk[j][0]
         for k in range(m):
            rikai[k] += bk[j][k+1]
   flag = True
   for j in rikai: 
      if j < x:
         flag = False
         break
   if flag:
      ans = min(ans,mon)
if ans == 10000000:
   ans = -1
print(ans)

Solution (Python):
import itertools
n,m,x=map(int,input().split())
l=[[0]]*n
ln=[0]*m
kan=0
for i in range(n):
  l[i]=list(map(int,input().split()))
  for j in range(m+1):
    if j==0:
      kan+=l[i][j]
    else:
      ln[j-1]+=l[i][j]
if sorted(ln)[0]<x:
  print(-1)
else:
  mkan=-1
  for i in range(n+1):
    itr=itertools.combinations(range(n),i)
    for comb in itr:
      kan=0
      ln=[0]*m
      for j in comb:
        kan+=l[int(j)][0]
        for ii in range(m):
          ln[ii]+=l[int(j)][ii+1]
      if sorted(ln)[0]>=x:
        if mkan==-1 or mkan>kan:
          mkan=kan
  print(mkan)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, X = MAP()
L = [LIST() for i in range(N)]

dp =[[0] * (1+M) for i in range(1+N)]

A = []
B = [0] * M
C = []
for l in L:
    c = l[0]
    C.append(c)
    A.append(l[1:])
    for i, a in enumerate(l[1:]):
        B[i] += a


for b in B:
    if b < X:
        print(-1)
        exit()

L = [0, 1] 
num = N 
bit_list = list(product([0, 1], repeat=N))

ma = INF
for bit in bit_list:
    bit = list(bit)
    
    
    l = [0] * M
    cost = 0
    for i, b in enumerate(bit):
        if b == 1:
            for m, a in enumerate(A[i]):
                l[m] += a
            cost += C[i]
    
    
    cnt = 0
    for k, b in enumerate(l):
        if b >= X:
            cnt += 1
    if cnt == M:
        
        
        ma = min(ma, cost)
print(ma)

Solution (Python):
N,M,X=map(int,input().split())
ans=-1
C=[]; A=[]
flag=[[]]*(1<<N)


for i in range(1<<N):
    d=[0]*N
    for j in range(N):
        if (i>>j)&1==1: d[j]=1
    flag[i]=d

for i in range(N):
    inp=list(map(int,input().split()))
    C.append(inp[0]); A.append(inp[1:])

for i in range(1<<N):
    f=flag[i]
    exp=[0]*M; yen=0
    for j in range(N):
        a=A[j]
        if f[j]==1:
            for k in range(M): exp[k]+=a[k]
            yen+=C[j]
    ok=True
    for j in range(M):
        if exp[j] < X: ok=False
    if ok: ans=min(ans,yen) if ans!=-1 else yen
print(ans)

Solution (Python):
import numpy as np
from itertools import combinations
N, M, X = map(int, input().split())
T = []
cost = 0
is_update = False
for _ in range(N):
    t = list(map(int, input().split()))
    cost += t[0]
    T.append(t)

for i in range(1, N+1):
    for c in combinations(T, i):
        c = np.array(c)
        _cost = c[:, 0].sum()
        if (c[:, 1:].sum(axis=0) >= X).all() and _cost <= cost:
            cost = _cost
            is_update = True
print(cost if is_update else -1)

Solution (Python):



import itertools as it


def main():
    N, M, X = map(int, input().split())

    book = []

    for n in range(N):
        book.append(list(map(int, input().split())))
    
    ok = False

    mini = 10**15
    for n in range(1, N+1):
        for v in it.combinations([x for x in range(1, N+1)], n):

            us = [0]*(M+1)
            flag = True
            for i in list(v):
                for j in range(1, M+1):
                    us[j] += book[i-1][j]
            for i in us[1:]:
                if i < X:
                    flag = False
                    break

            if flag:
                ok = True
                temp = 0
                for i in v:
                    temp += book[i-1][0]
                if mini > temp:
                    mini = temp
    
    if ok:
        print(mini)
    else:
        print(-1)
                    


if __name__ == '__main__':
    main()