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 numpy as np
N, M, X = map(int, input().split())
prices = []
effects = []
for i in range(N):
    c, *a = map(int, input().split())
    prices.append(c)
    effects.append(list(a))
 
prices = np.array(prices)
effects = np.array(effects)
 
 
ans = float("inf")
 
pats = []
for i in range(2 ** N):
    pat = bin(i).replace("0b", "")
    pat = "0" * (N - len(pat)) + pat
    pat = list(map(int, list(pat)))
    pats.append(pat)
    
pats = np.array(pats)
total_price = np.dot(pats, prices)
total_effects = np.dot(pats, effects)
cond = ((total_effects >= X).sum(axis=1) == M)
 
final = total_price[cond == 1]
if len(final) > 0:
    ans = int(final.min())
    print(ans)
else:
    print(-1)

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

a=[]

for i in range(0,n):
    aa=input().split()
    for j in range(0,m+1):
        aa[j]=int(aa[j])
    a.append(aa)

smin=1000000*n
d=1000000*n


for i in range(0,2**n):
    mo=0
    x2=[0 for i2 in range(0,m)]
    
    for j in range(0,n):
        if ((i>>j)&1)==1:
            mo+=a[j][0]
            for k in range(0,m):
                x2[k]+=a[j][k+1]

    if min(x2)>=x:
        if mo<smin:
            smin=mo
    

if smin==d:
    print(-1)

else:
    print(smin)

Solution (Python):
import numpy as np
import itertools

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


totallist=np.zeros((N,M+1))
for i in range(N):
    totallist[i]=list(map(int,input().split()))


lis=list(range(N))
result = []
print_value =float('inf')
total_test=np.zeros(M+1)
for n in range(1,len(lis)+1):
    for conb in itertools.combinations(lis, n):
        for i in conb:
            total_test=total_test+totallist[i]
            if(np.count_nonzero(total_test[1:]>=X)==M):
                if(print_value>=total_test[0]):
                    print_value=total_test[0]
        total_test=np.zeros(M+1)
if(print_value==float('inf')):
    print(-1)
else:
    print(int(print_value))

Solution (Python):
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(N)]
ans = 10**10
for i in range(2 ** N):
    total = 0
    point = [0 for _ in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            total += CA[j][0]
            for k in range(M):
                point[k] += CA[j][k+1]
    f = True
    for j in range(M):
        if point[j] < X:
            f = False
    if f:
        ans = min(ans, total)
if ans != 10 ** 10:
    print(ans)
else:
    print(-1)

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

books = list()
for _ in range(n):
    books.append(list(map(int, input().split())))


target = list()
result = -1

for i in range(2**n):
    score = [0] * m
    tmp = 0
    for j in range(n):
        bit = i >> (n-j-1) & 1
        if bit:
            score = [a + b for a, b in zip(score, books[j][1:])]
            tmp += books[j][0]

    if all([a >= x for a in score]):
        if result == -1:
            result = tmp
        else:
            result = min(result, tmp)

print(result)

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

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

min =10**10

for i in range(2**n):
    ii=i
    rikai=[0]*m
    kane=0
    for j in reversed(range(n)):

        if ii//(2**j)==1:
            ii-=(2**j)
            for k, a in enumerate(A[j]):
                if k==0:
                    kane+=a
                else:
                    rikai[k-1]+=a

    
    hantei=True
    for i in rikai:
        if i<x:
            hantei=False

    if hantei==True:
        if min > kane:
            min=kane

if min==10**10:
    print(-1)
else:
    print(min)

Solution (Python):
N,M,X = map(int,input().split())
item = []
result=[]
for x in range(N):
    C = list(map(int,input().split()))
    item.append(C)
n = len(item)
for i in range(2**n):
    A = [0]*M
    total = 0
    xx = 0
    for j in range(n):
        if ((i >> j) & 1):
            for m in range(M):
                A[m]+=item[j][m+1]
            total += item[j][0]
    for mm in range(M):
        if A[mm]>=X:
            xx+=1
    if xx==M:
        result.append(total)
if result==[]:
    print(-1)
    exit()
else:
    print(min(result))

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,x = inpm()
    c = [list(map(int,input().split())) for _ in range(n)]
    ans = float('inf')
    for num in range(1,n+1):
        for e in combinations(range(n),num):
            cost = 0
            under = [0 for _ in range(m)]
            for f in e:
                cost += c[f][0]
                for i in range(m):
                    under[i] += c[f][i+1]
            if min(under) >= x:
                ans = min(ans,cost)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

    
if __name__ == "__main__":
    main()

Solution (Python):
import itertools

books_num, alg_num, goal = map(int, input().split())
book = [[None]*(alg_num + 1) for _ in range(books_num)]

for i in range(books_num):
    book[i] = list(map(int, input().split()))


ans = float('inf')
seq = [i for i in range(books_num)]
flag = True
for i in range(books_num, 0, -1):
    if(not flag):
        break
    flag = False
    for seq_tmp in itertools.combinations(seq, i):
        skill = [0]*alg_num
        ans_tmp = 0
        for j in seq_tmp:
            for k in range(alg_num):
                skill[k] += book[j][k+1]
            ans_tmp += book[j][0]
            
            for k in range(alg_num):
                if skill[k] < goal:
                    break
            else:
                ans = min(ans, ans_tmp)
                flag = True
print(ans if ans != float('inf') else -1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 10 ** 10
for i in range(2 ** n):
    tmp = 0
    tmp_ca_sum = ca_sum.copy()
    for j, v in enumerate(format(i, r'0{}b'.format(n))):
        if v == '0':
            continue
        for k in range(m+1):
            tmp_ca_sum[k] -= ca[j][k]
    flag = True
    for v2 in tmp_ca_sum[1:]:
        if v2 < x:
            flag = False
            break
    if flag:
        ans = min(ans, tmp_ca_sum[0])

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

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

flag = False
ans = 10**10
for i in range(2 ** n):
    ans_lst = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            tmp = lst[j]
            for k in range(m + 1):
                ans_lst[k] += tmp[k]
        if all(score >= x for score in ans_lst[1:]):
            ans = min(ans, ans_lst[0])
            break

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

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

pair = []

for c1 in range(2):
    for c2 in range(2):
        for c3 in range(2):
            for c4 in range(2):
                for c5 in range(2):
                    for c6 in range(2):
                        for c7 in range(2):
                            for c8 in range(2):
                                for c9 in range(2):
                                    for c10 in range(2):
                                        for c11 in range(2):
                                            for c12 in range(2):
                                                pair.append([c1, c2, c3, c4, c5,c6, c7, c8, c9, c10, c11,c12])


zenkingaku = []
for pattern in pair:
    rikaido = [0 for _ in range(m)]
    kingaku = 0
    _pattern = pattern[:n]
    for ca_i, p in enumerate(_pattern):
        if p == 1:
            kingaku += ca[ca_i][0]
            for ca_j in range(m):
                rikaido[ca_j] += ca[ca_i][ca_j+1] 

    for ca_j in range(m):
        if rikaido[ca_j] < x:
            kingaku = -1

    if kingaku == -1:
        continue

    zenkingaku.append(kingaku)

if not zenkingaku:
    zenkingaku = [-1]
print(min(zenkingaku))

Solution (Python):
n,m,x =  list(map(int,input().split()))
c = [[]for _ in range(n)]
for i in range(n):
    c[i] = list(map(int,input().split()))
ans = float('inf')
for i in range(1,2**n):
    tmp = 0
    tmpl = [0 for _ in range(m)]

    for j in range(n):
        if((i>>j&1)):
            tmp += c[j][0]
            for k in range(1,m+1):
                tmpl[k-1] += c[j][k]
    ok = 0
    for l in range(m):
        if tmpl[l] >= x:
            ok += 1
    if ok >= m:
        ans = min([ans,tmp])

if ans != float('inf'):
    print(ans)
else:
    print(-1)

Solution (Python):
def main():
    from sys import stdin
    import itertools
    n,m,x = map(int,stdin.readline().rstrip().split())
    mat = []
    for _ in range(n):
        temp = list(map(int,stdin.readline().rstrip().split()))
        mat.append(temp)
    
    sum = []
    for i in range(n+1):
        for l in itertools.combinations(mat,i):
            temp = [0]*(m+1)
            for k in range(m+1):
                for j in l:
                    temp[k]+=j[k]
            sum.append(temp)
    
    sum.sort(key=lambda x: x[0])
    for l in sum:
        ans = -1
        flag = True
        for j in l[1:]:
            if j < x:
                flag = False
                break
        
        if flag:
            ans=l[0]
            break
    
    print(ans)
main()

Solution (Python):
import numpy as np
import itertools as it

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

CA = []

for i in range(N):
    CA.append( list(map(int, input().split())))

CA = np.array(CA)

def choice(N):
    ch = []
    for k in range(1,N+1):
        ch.append(list(it.combinations(range(N),k)))
    return list(it.chain.from_iterable( ch ))

ch = choice(N)
ans = 10**10

for c in ch:
    und = np.array( list(map( lambda i : sum(CA[c,i]), range(1,M+1))) )
    cost = sum(CA[c,0])
    if set( und >= X) == {True} and cost < ans:
        ans = cost

if ans == 10**10:
    ans = -1
    
print(ans)

Solution (Python):
n,m,x = map(int, input().split())
arr = []
money = []
vector = 0
for i in range(n):
  row = list(map(int, input().split()))
  money.append(row[0])
  arr.append(row[1:])
  vector += 2 ** (n-i-1)

ans = float('inf')
for i in range(vector+1):
  j = n-1
  result = [0] * m
  spend = 0
  while i > 0:
    if i % 2:
      result = [x + y for (x, y) in zip(result, arr[j])]
      spend += money[j]
    i //= 2
    j -= 1
  if min(result) >= x:
    ans = min(ans, spend)

if ans == float('inf'):
  print(-1)
else:
  print(ans)

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

L = 2**N
rlt = float('inf')
sk = [0]*M

for i in range(L):
  flag = 1
  tmp = 0
  tsk = [0]*M
  lst = bin(i)[2:].zfill(N)
  for j in range(N):
    if lst[j] == '1':
      
      tmp += CAs[j][0]
      for k in range(M):
        tsk[k] += CAs[j][k+1]
  for k in range(M):
    if tsk[k] < X:
      flag = 0
      break
  if flag == 1 and tmp < rlt:
    rlt = tmp

if rlt == float('inf'):
  print(-1)
else:
  print(rlt)

Solution (Python):
from itertools import combinations
N, M, X = map(int, input().split())
CA = [tuple(map(int, input().split())) for _ in range(N)]

ans = None
for n in range(1, N + 1):
    for cas in combinations(CA, n):
        atotals = [0] * M
        ctotal = 0
        for ca in cas:
            for i, a in enumerate(ca[1:]):
                atotals[i] += a
            ctotal += ca[0]
        if all(map(lambda atotal: atotal >= X, atotals)):
            if ans is None:
                ans = ctotal
            else:
                ans = min(ans, ctotal)
if ans is None:
    print(-1)
else:
    print(ans)

Solution (Python):

from itertools import combinations
from copy import deepcopy
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        books.append(list(map(int, input().split())))
    books_pattern = []
    books_num = [i for i in range(n)]
    for i1 in range(1, n + 1):
        books_pattern += list(combinations(books_num, i1))
    skill_set = []

    for ebp in books_pattern:
        skill_pattern = [0] * (m + 1)
        for ebpe in ebp:
            book_e = books[ebpe]
            for i2 in range(m + 1):
                skill_pattern[i2] += book_e[i2]
        skill_set.append(skill_pattern)

    skill_set_ok = []
    for ess in skill_set:
        tess = deepcopy(ess[1:])
        tessc = [i for i in tess if i >= x]
        if len(tessc) == m:
            skill_set_ok.append(ess[0])
    if len(skill_set_ok) > 0:
        print(min(skill_set_ok))
    else:
        print(-1)





if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, M, X = map(int, input().split())
    C = [list(map(int, input().split())) for i in range(N)]
    
    pCOST = float("inf")
    for bit in range(1<<N):
        COST = 0
        SJ = [0]*M
        for j in range(N):
            if bit>>j & 1:
            
                COST += C[j][0]
                for k in range(1,M+1):
                    SJ[k-1] += C[j][k]
        for l in range(M):
            if SJ[l] >= X:
                continue
            else:
                COST = float("inf")
                break
        pCOST = min(pCOST, COST)
    if pCOST == float('inf'):
        print(-1)
    else:
        print(pCOST)

if __name__ == '__main__':
    main()

Solution (Python):

from itertools import  product
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for _ in range(n)]
for i in range(1,m+1):
    count=0
    for j in range(n):
        count+=ca[j][i]
    if count<x:
        print(-1)
        exit()

ans=10**9



for z in product((0, 1), repeat=n):
    count=0
    count2=[0]*m
    for i in range(n):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,m+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(m):
        if count2[i]<x:
            break
    else:
        ans=min(count,ans)
print(ans)

Solution (Python):
N,M,X =map(int,input().split())
min_money = 10**9
books =[None]*N
for i in range(N):
    books[i] = list(map(int,input().split()))

for i in range(1<<N):
    output = []
    for j in range(N):
        if ((i>>j) & 1) == 1:
            output.append(1)
        else:
            output.append(0)

    money = 0
    gakusyuu = [0]*M
    for k in range(N):
        if output[k] == 1:
            money+=books[k][0]
            for l in range(1,M+1):
                gakusyuu[l-1]+=books[k][l]

    for i in range(len(gakusyuu)):
        if gakusyuu[i] < X:
            break
    else:
        if min_money>money:
            min_money = money

if min_money == 10**9:
    print(-1)
else:
    print(min_money)

Solution (Python):

import numpy as np
n, m, x = map(int, input().split())

cost = np.empty(n, dtype=int)
skill_up = np.zeros((n, m), dtype=int)

for i in range(n):
    l = list(map(int, input().split()))
    cost[i] = l[0]
    skill_up[i,:] = l[1:]

flag = False
min_cost = np.sum(cost)
for i in range(1, 2 ** n):
    bidx = bin(i)[2:].rjust(n, '0')
    mask = list(map(lambda x: x == '1', list(bidx)))
    skill = np.sum(skill_up[mask], axis=0)
    if np.all(skill >= x):
        flag = True
        min_cost = min(min_cost, np.sum(cost[mask]))

if not flag:
    min_cost = -1

print(min_cost)

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

ans=10**18
for i in range(1<<n):
  t_money=0
  t_rikai=[0]*m
  ok=True
  for j in range(n):
    if i&(1<<j): 
      t_money+=a[j][0]
      for k in range(m):
        t_rikai[k]+=a[j][k+1]
  for y,r in enumerate(t_rikai):
    if r>=x:
      pass
    else:
      ok=False
      break
  if ok:
    ans=min(t_money,ans)
  
if ans==10**18:
  print(-1)
else:
  print(ans)

Solution (Python):
num_books,m,min_understanding=list(map(int,input().split()))
info=[]
for _ in range(num_books):
    arr=list(map(int,input().split()))
    info.append(arr)

from itertools import combinations
l=[i for i in range(1,num_books+1)]
new=[]
for i in range(1,num_books+1):
    new.append(list(combinations(l,i)))

def add(l1,l2):
    faltu=[0 for i in range(len(l1))]
    
    
    for i in range(len(l1)):
        faltu[i]=l1[i]+l2[i]
    return faltu
def check(temp):
    
    ans=[0 for i in range(m+1)]
    for i in range(len(temp)):
        ans=add(ans,info[temp[i]-1])
    for i in range(1,len(ans)):
        if ans[i]>=min_understanding:
            continue
        else:
            return 999999999
    return ans[0]
tempo=[]
for i in new:
    for j in i:
        tempo.append(check(j))
if min(tempo)==999999999:
    print(-1)
else:
    print(min(tempo))

Solution (Python):



def ad(l,x):
	for i in range(1,len(l)+1):
		l[i-1]+=x[i]
from itertools import combinations
n,m,X=map(int,input().split())
l=[]
for i in range(n):
	l.append([int(x) for x in input().split()])
l.sort()
comb=[i for i in range(n)]
ml=[0]*m
cost=10**9
for i in range(1,n+1):
	coco=list(combinations(comb,i))
	for j in range(len(coco)):
		ml=[0]*m
		c=0
		for k in range(len(coco[j])):
			c+=l[coco[j][k]][0]
			ad(ml,l[coco[j][k]])
			
			if min(ml)>=X:
				cost=min(c,cost)
				break
		if min(ml)>=X:
			cost=min(c,cost)

if cost==10**9:
	print(-1)
else:
	print(cost)

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

mini_cash=12*10**5+2

for alllist in list(itertools.product([0,1], repeat=n)):
    
    temp_mini_cash=0
    knowledge = [0]*m
    j = 0
    for i in alllist:
        if i==1:
            for k in range(m):
                knowledge[k]+=Text[j][1+k]
                
            temp_mini_cash +=Text[j][0]
        j+=1
    
    
    if all([i >= x for i in knowledge]):
        if temp_mini_cash<mini_cash:
            mini_cash=temp_mini_cash
if mini_cash!=12*10**5+2:
    print(mini_cash)
else:print("-1")

Solution (Python):
N, M, X = list(map(int, input().split()))

C = []
A = []

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

C2 = []
A2 = []

for i in range(2**N):
    su = [0]*M
    sai = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M):
                su[k] += A[j][k]
            sai += C[j]
    C2.append(sai)
    A2.append(su)

ans = 10000000000

for i in range(len(A2)):
    flag = True
    for j in A2[i]:
        if j < X:
            flag = False
    if flag:
        if ans > C2[i]:
            ans = C2[i]

if ans == 10000000000:
    print(-1)
else:
    print(ans)

Solution (Python):
import copy
from itertools import combinations

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

books = []

for i in range(N):
    books.append(list(map(int, input().split())))

combi = []

for i in range(1, len(books) + 1):
    for conb in combinations(books, i):
        combi.append(list(conb))

min_result = None
for i in combi:
    result = copy.deepcopy(i[0])

    for j in i[1:]:
        for k in range(len(j)):
            result[k] += j[k]

    flag = True

    for j in result[1:]:
        if j < X:
            flag = False
            break

    if flag and (min_result is None or min_result > result[0]):
        min_result = result[0]

if min_result is None:
    print(-1)
else:
    print(min_result)

Solution (Python):

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

ans=-1
for i in range(2**N):
    skill=[0 for i in range(M)]
    cost=0
    flg=True
    for j in range(N):
        if i >> j &1:
            cost+=C[j]
            for k in range(M):
                skill[k]+=A[j][k]
    
    for k in range(M):
        if skill[k]<X:
            flg=False
    if flg:
        if ans==-1:
            ans=cost
        else:
            ans=min(ans,cost)

print(ans)

Solution (Python):
import itertools
N, M, X = map(int, input().split())
books = list()
tst = [0] * M
for _ in range(N):
    C, *A = map(int, input().split())
    books.append((C, A))
    for i, aa in enumerate(A):
        tst[i] += aa
if len([t for t in tst if t < X]) > 0:
    print("-1")
    exit()
r = None
for i in range(1, N+1):
    for j in itertools.combinations(range(len(books)), i):
        cost = 0
        tst = [0] * M
        for b in j:
            co, ms = books[b]
            cost += co
            for i, aa in enumerate(ms):
                tst[i] += aa
        if len([t for t in tst if t < X]) == 0:
            if r is None or r > cost:
                r = cost
print(r)

Solution (Python):
n,m,x = map(int,input().split())
A = [[] for _ in range(n)]
for i in range(n):
    A[i] = list( map(int,input().split()) )
    
flag = 0
min_charge = 10**7

for i in range(2**n):
    which = format(i, '
    
    
    
    charge = 0
    skill = [0 for _ in range(m)]
    for j in range(n):
        if which[j]=='1':
            charge += A[j][0]
            for k in range(m):
                skill[k]+=A[j][k+1]
    flag_skill = 1
    for l in range(m):
        if skill[l] < x:
            flag_skill = 0
    
    
    
    
    
    if flag_skill ==1:
        min_charge = min(min_charge,charge)
    
    

if min_charge == 10**7:
    print(-1)
else:
    print(min_charge)

Solution (Python):
from itertools import combinations
import numpy as np
def main():
    n, m, x = map(int, input().split())
    lst = []
    for _ in range(n):
        tmp = list(map(int, input().split()))
        lst.append(tmp)
    
    bango = [i for i in range(n)]
    k = 1
    minkingaku = float('inf')
    flag = False
    while k <= n:
        combs = combinations(bango, k)
        for comb in combs:
            
            algo = np.zeros(m)
            kingaku = 0
            for c in comb:
                algo += np.array(lst[c][1:])
                kingaku += lst[c][0]
            
            if (algo >= x).all():
                flag = True
                if kingaku <= minkingaku:
                    minkingaku = kingaku
            

        k += 1
    if flag:
        print(minkingaku)
    else:
        print('-1')
main()

Solution (Python):
import itertools

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

C = []
A = []

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

ans = -1

queue = [[0, 0, [0] * M]]
while queue:
    index, price, study_list = queue.pop(0)

    if index < N:
        queue.append([index + 1, price, study_list])

        price_2 = price + C[index]
        study_list_2 = study_list[:]
        for i in range(M):
            study_list_2[i] += A[index][i]

        queue.append([index + 1, price_2, study_list_2])
    else:
        flag = True
        for s in study_list:
            if s < X:
                flag = False
                break
        if flag:
            if ans == -1:
                ans = price
            else:
                ans = min(ans, price)
print(ans)

Solution (Python):
import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n, m, x = MI()
    li = [LI() for _ in range(n)]

    min = float(inf)
    for i in range(2 ** n):
        flag = True
        total = [0] * (m + 1)
        for j in range(n):
            if (i >> j) & 1:
                total = [x + y for (x, y) in zip(total, li[j])]

        for t in total[1:]:
            if t < x:
                flag = False

        if flag:
            if total[0] < min:
                min = total[0]

    if isinstance(min, float):
        print(-1)
    else:
        print(min)


if __name__ == "__main__":
    main()

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

n, m, k = map(int, input().split())
a = []
r = []
now = []

def f(i):
    global n, k
    flag = 0

    if i + 1 == n:
        if min(now[1:]) >= k:
            r.append(now[0])
        return

    f(i + 1)

    for x in range(m + 1):
        now[x] += a[i + 1][x]

    f(i + 1)

    for x in range(m + 1):
        now[x] -= a[i + 1][x]
    

for x in range(n):
    b = [int(y) for y in input().split()]
    a.append(b)

now = a[0]
f(0)

now = [0] * (m + 1)
f(0)

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

Solution (Python):


n, m, x = [0] * 3
c = []
a = []

def format_input(filename = None):
	global n, m, x
	global c
	global a
	if filename == None:
		n, m, x = list(map(int, input().split()))
		ca = [list(map(int, input().split())) for i in range(n)]
		for i in ca:
			c.append(i[0])
			a.append(i[1:])

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 12)
		m = rng(1, 12)
		x = rng(1, 10**5)
		c = [rng(1, 10**5) for i in range(n)]
		a = [[rng(1, 10**5) for j in range(m)] for i in range(n)]
		print(n, m, x)
		[print(c[i], ' '.join(list(map(str, a[i])))) for i in range(n)]

def get_answer():
	answer = sum(c) + 1

	for k in range(2**n):
		understand = [0] * m
		price = 0
		bit = k
		i = 0
		while bit != 0:
			for j in range(m):
				understand[j] += a[i][j] * (bit & 1)
			price += c[i] * (bit & 1)
			bit >>= 1
			i += 1
		check = True
		for j in range(m):
			if understand[j] < x:
				check = False
		if check:
			answer = min(answer, price)

	if answer == sum(c) + 1:
		answer = -1

	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Solution (Python):
import copy
from functools import lru_cache
n, m, x = map(int, input().split())

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

mn = float('inf')
smart = [0] * m

def good():
    global x, smart

    for kn in smart:
        if kn < x:
            return False
    
    return True

@lru_cache(maxsize=None)
def solve(idx, n, sm):
    global mn, books, smart

    if idx == n:
        if good():
            
            mn = min(mn, sm)
        return

    

    cur_books = books[idx][1]
    cost = books[idx][0]
    for i in range(len(smart)):
        smart[i] += cur_books[i]

    solve(idx + 1, n, sm + cost)

    for i in range(len(smart)):
        smart[i] -= cur_books[i]

    solve(idx + 1, n, sm)


solve(0, n, 0)

print(mn if mn != float('inf') else -1)

Solution (Python):
def resolve():
    N, M, X = map(int, input().split())
    L = []*M
    ans = 10000000000
    for i in range(N):
        L.append(tuple(map(int, input().split())))

    for i in range(2 ** N):
        s = 0
        C = [0]*M
        for j in range(N):
            if (i >> j) & 1:
                C = [a+b for (a, b) in zip(C, L[j][1:])]
                s += L[j][0]
        CC = len([c for c in C if c >= X])
        if CC == M:
            ans = min(ans, s)
    print(-1 if ans == 10000000000 else ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
N,M,X = map(int,input().split())
C=[0]*N
A=[[0]*M for i in range(N)]


for i in range(N):
    hon = list(map(int,input().split()))
    C[i]=hon[0]
    for j in range(M):
        A[i][j] = hon[j+1]
rikaido=[0]*M
ans = 20*(10**5)
for i in range(2**N):
    pattern=[0]*N
    temp = 0
    rikaido=[0]*M
    for j in range(N):
        if (i >> j & 1):
            for k in range(M):
                pattern[j] =1
                rikaido[k]+=A[j][k]
            temp+=C[j]
    flag = 0
    for i in range(M):
        if rikaido[i] < X:
            flag = 1
    if flag ==0 and temp < ans:
        ans = temp

if ans == 20*(10**5):
    print(-1)
else:
    print(ans)

Solution (Python):
import copy
N, M, X = map(int, input().split())


C =[]
A = {}

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

bestscore = 99999999999
def rec(n, score, money):
    global bestscore
    if n==N: return
    s = copy.deepcopy(score)
    rec(n+1, s, money)

    money += C[n]
    for i in range(M):
        score[i] += A[n][i]
    

    for i in range(M):
        if score[i] < X:
            s = copy.deepcopy(score)
            rec(n+1, s, money)
            return
    bestscore = min(bestscore, money)

score = [0 for i in range(M)]

rec(0, score, 0)
if bestscore == 99999999999:
    print(-1)
else:
    print(bestscore)

Solution (Python):
n, m , x = map(int, input().split())
c, a = [], []
for _ in [0]*n:
    temp = list(map(int, input().split()))
    c.append(temp[0])
    a.append(temp[1:])

sign = (1, 0)

ans = float("inf")
import numpy as np
from itertools import product
for i in product(sign, repeat = n):
    temp = np.zeros(m)
    cc = 0
    for j in range(n):
        tt = a[j]
        if i[j] == 1:
            temp += tt
        cc += c[j] * i[j]

    if np.all(temp >= x):
        ans = min(ans, cc)

print(ans if ans != float("inf") else -1)