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):
n, m, x = map(int, input().split())
P = [list(map(int, input().split())) for i in range(n)]

INF = 10 ** 9
ans = INF
for bit in range(1 << n):
    now = 0

    Q = [0]*m
    for i in range(n):
        if bit >> i & 1:
            now += P[i][0]
            for j in range(m):
                Q[j] += P[i][j+1]

    ok = 1
    for j in range(m):
        if Q[j] < x:
            ok = 0

    if ok == 1:
        ans = min(ans, now)

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

Solution (Python):
import itertools

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

l = []
for i in range(n):
    l.append([int(x) for x in input().split()])

p = list(itertools.product([0, 1], repeat=n))

lc = []
for i in range(2 ** n):
    list_sum_k = []
    for k in range(1, m+1):
        sum_c = 0
        sum_k = 0
        for j in range(n): 
            if p[i][j] == 1: 
                sum_c += l[j][0]
                sum_k += l[j][k]
        list_sum_k.append(sum_k)
    
    
    if all(k >= x for k in list_sum_k):
        
        lc.append(sum_c)
        

if not lc:
    print('-1')
else:
    print(min(lc))

Solution (Python):
def main():
    n,m,x = map(int,input().split())
    A = []
    ans = 10**9
    for i in range(n):
        tmp = [int(i) for i in input().split()]
        A.append(tmp)
    for i in range(2**n):
        arg = [0 for j in range(m+1)]
        cost = 0
        for j in range(n):
            if (i>>j)&1 ==1:
                cost += A[j][0]
                for k in range(1,m+1):
                    arg[k] += A[j][k]
        flag = True
        for k in range(1,m+1):
            if arg[k]<x:
                flag = False
                break
        if flag:
            ans = min(ans,cost)
    if ans==10**9:
        print('-1')
    else:
        print(ans)
main()

Solution (Python):
n ,m,x = map(int,input().split())
a = [None] * n
c = [None] * n
ans = float('inf')
for i in range(n):
    a[i] = list(map(int,input().split()))
    c[i] = a[i][0]
    a [i] = a[i][1:]
for i in range(2 ** n):
    rikai = [0] * m
    kane = 0
    bi = format(i,'012b')
    for j in range(n):
        if (i >> j)%2 == 1:
            kane += c[j]
            rikai = [rikai[f] + a[j][f] for f in range(m)]
    if all(rikai[f] >= x for f in range(m)):
        ans = min(ans,kane)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
import numpy as np





def main():
    (N, M, X) = map(int, input().split())
    A = np.zeros((N,M+1), dtype='int32')
    for i in range(N):
        A[i] = list(map(int, input().split()))
    
    A = A[np.argsort(A[:,0])]

    i = 0
    m = -1
    while i < 2**N:
        i += 1
        c = 0
        sum = np.zeros(M, dtype='int32')
        for j in range(N):
            if i & 2**j == 2**j:
                c += A[j][0]
                sum += A[j][1:]
        if np.all(sum >= X):
            m = c if m < 0 else min(m, c)
    
    print(m)
main()

Solution (Python):
def check(learn_total):
    for i in range(m):
        if learn_total[i] < x:
            return False
    return True
 
 
def calc_price(bit):
    price_total = 0  
    learn_total = [0] * m  
 
    for i in range(n):
        if (bit >> i) & 1:  
            price_total += c[i]  
            learn = a[i]  
            for j, le in enumerate(learn):  
                learn_total[j] += le
 
    
    if check(learn_total):
        return price_total
    else:
        return INF
 
 
if __name__ == '__main__':
    INF = float("inf")
 
    n, m, x = list(map(int, input().split()))
 
    
    c = []  
    a = []  
 
    for i in range(n):
        c_temp, *a_temp = list(map(int, input().split()))  
        c.append(c_temp)
        a.append(a_temp)
 
    ans = INF
 
    for bit in range(1 << n):
        price = calc_price(bit)  
        ans = min(ans, price)  
 
    if ans == INF:
        print(-1)
    else:
        print(ans)

Solution (Python):

N, M, X = map(int, input().split())
C = []
A = []
for  i in range(N):
    t = list(map(int, input().split()))
    C.append(t[0])
    A.append(t[1:])
    
result = -1
"""
<< bit演算に関する演算子
左辺の値を右辺の値だけ左へシフトすることを意味する

https://www.javadrive.jp/python/num/index4.html

下記の場合、1からNまで2真数でシフトしていく感じ
"""

for i in range(1 << N):
    
    t = [0] * M
    c = 0
    
    for j in range(N):
        
        if(i >> j ) & 1 == 0 :
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

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

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

ans = -1



for i in range(1 << N):

    study = [0] * M
    cost = 0

    
    
    for j in range(N):

        
        if (i >> j) & 1:
            cost += C[j]

            
            for m in range(M):
                study[m] += A[j][m]

    
    if min(study) >= X:
        if ans == -1:
            ans = cost
        else:
            ans = min(ans, cost)

print(ans)

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

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

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

A = np.array(A)

L = list(it.product([0,1], repeat = N))

saishoucost = 100000000
Check = 0

for i in range (0, len(L)):
	D = np.array([0]*(M+1))
	Check = 0
	for j in range (0, N):
		if L[i][j] == 1:
			for k in range (0, M+1):
				D[k]+=A[j][k]
	for j in range (1, M+1):
		if D[j] < X:
			Check = 1
	if Check == 0:
		saishoucost = min(saishoucost, D[0])

if saishoucost == 100000000:
	print(-1)
else:
	print(saishoucost)

Solution (Python):
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N,M,X=MI()
C=[]
A=[]
for i in range(N):
  L=LI()
  C.append(L[0])
  A.append(L[1:])
ans=-1
for i in range(1<<N):
  tmp=[0]*M
  cost=0
  for j in range(N):
    if 1&(i>>j):
      cost+=C[j]
      for m in range(M):
        tmp[m]+=A[j][m]
  if min(tmp)>=X:
    if ans==-1:
      ans=cost
    else:
      ans=min(ans,cost)
print(ans)

Solution (Python):
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N,M,X=MI()
List=[]
for i in range(N):
  CA=LI()
  List.append(CA)
ans=-1
for i in range(1<<N):
  tmp=[0]*M
  cost=0
  for j in range(N):
    if 1&(i>>j):
      cost+=List[j][0]
      for k in range(M):
        tmp[k]+=List[j][k+1]
      if min(tmp)>=X:
        if ans==-1:
          ans=cost
        else:
          ans=min(ans,cost)
print(ans)

Solution (Python):

n,m,x=list(map(int,input().split()))
a=[]
l=[]
for i in range(n):
    p=list(map(int,input().split()))
    l.append(p)
for i in range(1,2**n):
    k=0
    ar=[0]*m
    for j in range(n):
        if (i>>j)&1==1:
            
            k+=l[j][0]
            for u in range(m):
                ar[u]+=l[j][u+1]
    
    if min(ar)>=x:
        a.append(k)
if len(a)>0:
    print(min(a))
else:
    print(-1)

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


def rikaido(lst):
    a = []
    for i in range(m):
        s = 0
        for j in range(len(lst)):
            s += lst[j][i]
        a.append(s)
    
    return min(a)


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

ans = 10000000
for i in range(2 ** n):
    if i == 0:
        continue
    lst = []
    cost = 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            lst.append(a[j])
            cost += c[j]
    
    if rikaido(lst) >= x:
        ans = min(ans, cost)

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

Solution (Python):
import itertools
import numpy as np
n,m,x=map(int,input().split())
li=np.array([list(map(int,input().split())) for i in range(n)])
ln=[j for j in range(n)]
ans=[]
for j in range(1,n+1):
    la=list(itertools.combinations(ln, j))
    for k in la:
      ls=np.zeros(m+1, dtype = int) 
      for l in range(len(k)):
        ls=ls+li[k[l]]
      lsp=[i for i in ls[1:] if i>=x]  
      if len(lsp)==m:
        ans.append(ls[0])
if ans==[]:
  print(-1)
else:
  print(min(ans))

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline

N,M,X = list(map(int,input().split()))
CA = [ list(map(int,input().split())) for _ in range(N)]
bit = 2**N
cost = float('inf')

for bi in range(1,bit):
    tmp=[]
    for i in range(N):
        if bi & 1<<i:
            tmp.append(CA[i-1])
    tmp = np.array(tmp)        
    a = sum(tmp)
    if all( [a[j]>=X for j in range(1,M+1)]):
        cost = min(cost,a[0])
print( -1 if cost == float('inf') else cost)

Solution (Python):
n,m,x=map(int,input().split())
cost=[]
kekka=[]
res=[]
for _ in range(n):
    a=list(map(int, input().split()))
    cost+=[a[0]]
    kekka+=[a[1:]]
for i in range(2**n):
    sum=[0]*m
    money=0
    ok=1
    for j in range (n):
        if i>>j & 1:
            for k in range(m):
                sum[k]+=kekka[j][k]
            money+=cost[j]
    for l in sum:
        if l < x:ok=0
    if ok==1:res += [money]
print("-1" if res == [] else min(res))

Solution (Python):
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for i in range(n)]
ans = 10 ** 15
for i in range(2 ** n):
  rikai = [0] * m
  money = 0
  for j in range(n):
    if (i >> j) & 1:
      for k in range(m):
        rikai[k] += ca[j][k+1]
      money += ca[j][0]
  if min(rikai) >= x:
    ans = min(ans, money)
if ans == 10 ** 15:
  print(-1)
else:
  print(ans)

Solution (Python):
import itertools
import numpy as np
 
N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
sumX = sum(ca)[1:]
sumcos = sum(ca)[0]
cost = sumcos
if sum(sumX>=X)<M:
    print(-1)
else:
    for j in range(1,N+1):
        for a in itertools.combinations(range(1,N+1),j):       
            x = sum(ca)[1:]
            fx = np.array([0]*M)
            c = sumcos
            for i in range(len(a)):
                x -= ca[a[i]-1][1:]
                c -= ca[a[i]-1][0]
                if sum(x>=X)<M:
                    break
                else:
                    cost = min(c,cost)
    print(cost)

Solution (Python):


import itertools




def main():
    n, m, x = input_list()
    books = {}
    contents = {}
    for i in range(n):
        c = input_list()
        books[i] = c[0]
        contents[i] = c[1:m+1]

    if n == 1:
        if sum(contents[0]) >= x:
            print(books[0])
        else:
            print(-1)
        exit()

    ans = []
    for v in itertools.product([0, 1], repeat=n):
        understands = [0] * m
        ok = [False] * m
        a = 0
        for i, vi in enumerate(v):
            if vi == 0:
                continue
            for index, val in enumerate(contents[i]):
                understands[index] += val
                if understands[index] >= x:
                    ok[index] = True
            a += books[i]
        if all(ok):
            ans.append(a)

    if len(ans) > 0:
        print(min(ans))
    else:
        print(-1)
        
        
        
        
        
        
        
        
        


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

def dfs(i, cost, A):
    if i == n-1:
        global ans
        if cost < ans and all([ai>=x for ai in A]):
            ans = cost
        return
    
    i += 1
    dfs(i, cost, A[:])
    dfs(i, cost+c[i], A[:]+a[i])

    
        
        

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c, a = [None]*n, np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**20
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**20:
        print(-1)
    else:
        print(ans)

Solution (Python):
from sys import exit
import numpy as np





N,M,X =map(int, input().split())
C=[list(map(int, input().split())) for _ in range(N)]

tmp=float("inf")

for i in range(2**N):
    s=np.zeros(M+1)
    for j in range(N):
        if (i>>j)&1 :
            s+=C[j]
    if min(s[1:])>=X:
        tmp=min(s[0],tmp)

if tmp==float("inf"):
    tmp=-1
print(int(tmp))

Solution (Python):
N, M, X = map(int, input().split())
alist = [ list(map(int,input().split())) for _ in range(N)]
ans = float('inf')
for i in range(2**N):
  current = [0]*(M+1)
  for j in range(N):
    if (i>>j)&1:
      for k in range(M+1):
        current[k]+=alist[j][k]
  if X<= min(current[1:]) and current[0]<ans:
    ans = current[0]
print(-1 if ans==float('inf') else ans)

Solution (Python):
n,m,x = map(int,input().split())
ls = []
mi = 10**18
for i in range(n):
  ls.append(list(map(int,input().split())))
for i in range(2**n+1):
  cost = 0
  f = "{{:0{}b}}".format(n)
  now = f.format(i)
  understand = [0]*m
  for j in range(len(now)):
    if now[j] == "1":
      cost += ls[j][0]
      for k in range(m):
        understand[k] += ls[j][k+1]
  if min(understand) >= x:
    if mi > cost:
      mi = cost
if mi == 10**18:
  print(-1)
else:
  print(mi)

Solution (Python):
import sys
n, m, x = map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
mn=10**18
for mask in range(1<<n):
    l=[0]*(m+1)
    for i in range(n):
        if ((mask>>i)&1)==0:
            for j in range(m+1):
                l[j]+=c[i][j]
    count=0
    for k in range(1,m+1):
        if l[k]>=x:
            count+=1
    if count==m:
        mn=min(mn,l[0])

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

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

buy = list(itertools.product([0,1],repeat=n))

money = []

for i in range(len(buy)):
    algo = [0 for _ in range(m)]
    money_tmp = 0
    
    for j in range(len(buy[i])):
        for k in range(m):
            algo[k] += book[j][k+1] * buy[i][j]
        money_tmp += book[j][0]*buy[i][j]
    
    if min(algo) >= x:
        money.append(money_tmp)
        
if len(money) > 0:    
    print(min(money))
else:
    print(-1)

Solution (Python):


import sys

def main():
    input = sys.stdin.readline
    n,m,x = map(int, input().split())
    c = []
    a = []
    for i in range(n):
        row = list(map(int, input().split()))
        c.append(row[0])
        a.append(row[1:])
    min_price = -1
    for nbit in range(1<<n): 
        sum_price = 0
        sum_a = [0]*m
        for i in range(n):
            if nbit>>i & 1:
                for j in range(m):
                    sum_a[j] += a[i][j]
                sum_price += c[i]
        if sum_price == 0:
            continue
        elif all(value >= x for value in sum_a):
            if min_price == -1:
                min_price = sum_price
            elif sum_price < min_price:
                min_price = sum_price
    
    print(min_price)
    return


if __name__ == '__main__':
    main()

Solution (Python):
n, m, x = map(int, input().split())
al = []
cl = []
for i in range(n):
    al.append(list(map(int, input().split())))
    cl.append(al[i].pop(0))

ans = []
for i in range(2**n):
    books = []
    for j in range(n):
        if i>>j & 1:
            books.append(j)

    a = True
    for alg in range(m):
        und = 0
        for b in books:
            und += al[b][alg]
        if und < x:
            a = False
            break
    if a:
        cost = 0
        for b in books:
            cost += cl[b]
        ans.append(cost)

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

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

books = [0] * n
for _ in range(n):
    books[_] = list(map(int, input().split()))

ans = -1
ans_list = []
for i in range(1<<n):
    money = 0
    cleared = 0
    level = [0]*m
    for j in range(n):
        if i>>j & 1:
            money += books[j][0]
            for book in range(m):
                level[book] += books[j][book+1]

    level.sort()
    if level[0] >= x:
        ans_list.append(money)

if len(ans_list) > 0:
    ans = min(ans_list)

print(ans)

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

skill = [0]*M
flag = [0]*M    
saisyou = 10**7
for p in range(2**N):
    for q in range(N):
        if p >> q & 1:      
            money += C[q][0]
            for r in range(M):  
                skill[r] += C[q][r+1]
    for s in range(M):
        if skill[s] >= X:
            flag[s] = 1
    if 0 not in flag and money < saisyou:
        saisyou = money
    money = 0
    skill = [0]*M
    flag = [0]*M
if saisyou == 10**7:
    saisyou = -1
print(saisyou)

Solution (Python):
n,m,x=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(n):
  ca=[int(x) for x in input().rstrip().split()]
  l.append(ca)

ans=float('inf')
for i in range(2**n):
  now=0
  under=[0]*m
  for j in range(n):
    if i>>j & 1:
      now+=l[j][0]
      for s in range(m):
        under[s]+=l[j][s+1]

  cnt=0
  for u in under:
    if x<=u:
      cnt+=1
  
  if cnt==m:
    ans=min(ans,now)

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

Solution (Python):
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
ans = float('inf')
for mask in range(1,1<<N):
    tmp = [0]*M
    money = 0
    for i in range(N):
        if mask>>i & 1:
            for j in range(M):
                tmp[j]+=A[i][j+1]
            money+=A[i][0]
    if min(tmp)>=X:
        ans = min(ans,money)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
from itertools import product

N,M,X = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]
 
DEF_VAL = 99999999
min_cost = DEF_VAL
for rows in product([True, False], repeat=N):
    cost = 0
    x = [0] * M
    for i in range(N):    
        if rows[i]:
            cost += data[i][0]
            for c in range(M):
                x[c] += data[i][c+1]
    if min(x) >= X and cost < min_cost:
        min_cost = cost

if min_cost == DEF_VAL:
    print(-1)
else:
    print(min_cost)

Solution (Python):
import itertools

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

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

max = 2**n
ans = 10**18
for i in range(max) :
    num = i
    cost = 0
    r = [0]*m
    check = 0
    for j in range(n) :
        f = num%2
        num = num//2
        if f == 0 :
            continue
        cost += c[j]
        r = [x+y for (x,y) in zip(r,a[j])]
    if all(elem >= x for elem in r) :
        ans = min(ans,cost)

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

Solution (Python):
import numpy as np
n,m,x=map(int,input().split())
c=[]
a=[]
for i in range(n):
    d=list(map(int,input().split()))
    c.append(d[0])
    a.append(d[1:])



chk=np.zeros(m)
ans=10**9
for j in range(2**n):
    t=0
    s=np.zeros(m)
    for i in range(n):
        if j>>i&1:
            t+=c[i]
            for k in range(m):
                s[k]+=a[i][k]
            if min(s)>=x:
                ans=min(ans,t)

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

Solution (Python):
from itertools import *

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

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




res = []

for a in product((0,1), repeat=N):
    P = [0] * M
    cost = 0
    for i in range(N):
        if a[i]:
            cost += C[i]
            for j in range(M):
                P[j] += A[i][j]
    for j in range(M):
        if P[j] < X:
            break
        if j == M-1:
            res.append(cost)

if not res:
    print(-1)
else:
    print(min(res))

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()))
ans = 10**9
for x in range(1,1<<N):
    C = [0]*M
    cost = 0
    for i in range(N):
        if x>>i&1==1:
            for j in range(M):
                C[j] += A[i][j+1]
            cost += A[i][0]
    if all([c>=X for c in C]):
        ans = min(ans,cost)
if ans==10**9:
    ans = -1
print(ans)

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

li = []
for i in range(m):
    li.append([])

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

ans = sum(money) + 1
first = ans

for hh in range(1 << n):
    cnt = 0
    for i in range(m):
        s = 0
        for h in range(n):
            if (hh >> h)%2 == 1:
                continue
            s += li[i][h]
        if s >= x:
            cnt += 1
    if cnt == m:
        an = 0
        for h in range(n):
            if (hh >> h)%2 == 1:
                continue
            an += money[h]
        ans = min(ans, an)

if ans == first:
    ans = -1

print(ans)

Solution (Python):

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

c = []

ans = 10**9

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

for i in range(2**n):
    t = []
    r = [0]*m
    cost = 0
    for s in range(n):
        if i >> s & 1:
            t.append(s)
    
    for tx in t:
        cost += c[tx][0]
        for x in range(m):
            r[x] += c[tx][x+1]

    if min(r)>xm-1:
        ans = min(ans,cost)

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

Solution (Python):
N,M,X = map(int,input().split())
A = []
cost = []
for i in range(N):
    a = list(map(int,input().split()))
    A.append(a[1:])
    cost.append(a[0])
ans = float('inf')
for i in range(2**N):
    I = bin(i)[2:]
    I = I.zfill(N)
    tmp = [0]*M
    buy = 0
    for j in range(len(I)):
        if I[j]=='1':
            for k in range(len(A[j])):
                tmp[k] += A[j][k]
            buy += cost[j]
    if all(tmp[i]>=X for i in range(len(tmp))):
        ans = min(ans,buy)
ans = -1 if ans ==float('inf') else ans
print(ans)

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

INF = 10**8
N,M,X=map(int, input().split())
C = []
A = [[0 for i in range(M)] for j in range(N)]

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

C, A = map(np.array, [C,A]) 
min_ = INF
for i in range(1,N+1):
  for c in combinations(range(N),i):
    if (A[c,:].sum(0) >= X).sum() == M:
      if C[list(c)].sum() < min_:
        min_ = C[list(c)].sum()

if min_ == INF: print(-1)
else: print(min_)

Solution (Python):
n,m,x = map(int, input().split())
ref = []
c = []
for i in range(n):
  ref.append(list(map(int, input().split())))
  c.append(ref[i].pop(0))
ans = sum(c)
ok = False
for i in range(1<<n):
  cost = 0
  skill = [0]*m
  for r,j in enumerate(ref):
    if (i>>r)&1 == 1:
      cost += c[r]
      for k in range(m):
        skill[k] += j[k]
  if min(skill)>=x:
    ok = True
    if cost < ans:
      ans = cost
if ok:
  print(ans)
else:
  print(-1)

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

ans=10**18
for BIT in range(1<<n):
    l=[0]*m
    tmp=0
    t=0
    b="0"*(n-len(bin(BIT)[2:]))+bin(BIT)[2:]
    book=[]
    for i in range(n):
        if b[-i-1]=="1":
            book.append(i)
    
    for j in range(n):
        if j in book:
            for k in range(1,m+1):
                l[k-1]+=ca[j][k]
            tmp+=ca[j][0]
    
    for z in range(m):
        if l[z]<x:
            t=1
            continue
    if t==1:
        continue
    if ans>tmp:
        ans=tmp
    
if ans==10**18:
    print(-1)
else:
    print(ans)

Solution (Python):

import heapq

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

for i in range(2**N):
  cost = 0
  rikaido = [0] * (M)
  sankosyo = list()
  for j in range(N):
    if (i >> j) & 1:
      
      sankosyo.append(j)
      cost += C[j]
  for k in sankosyo:
    for l in range(M):
      rikaido[l] += A[k][l]
  if min(rikaido) >=  X:
    heapq.heappush(h, cost)
if len(h) > 0:
  print(h[0])
else:
  print(-1)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(1000000)

def dfs(cost, i, A):
    if i == n-1:
        global ans
        if cost < ans and all([ai>=x for ai in A]):
            ans = cost
        return
    i += 1
    dfs(cost, i, A)
    dfs(cost+c[i], i, A+a[i])

    

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c, a = [None]*n, np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**10
    dfs(0, -1, np.array([0]*m))
    if ans == 10**10:
        print(-1)
    else:
        print(ans)

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

C = [0] * N
A = [x for x in range(M)] * N

for i in range(N):
    tmp = [int(x) for x in input().split()]
    C[i] = tmp[0]
    A[i] = tmp[1:]
min = sum(C) + 1

for i in range(2**N):
    cost = 0
    ANS = [0]*M

    for j in range(N):
        if((i>>j) & 1):
            cost += C[j]
            for k in range(M):
                ANS[k] += A[j][k]

    
    ans = 1
    for j in ANS:
        if(j < X):
            ans = 0


    if(ans and cost < min):
        min = cost


if(min == sum(C)+1):
    print(-1)
else:
    print(min)

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

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

ans = 10**30
for i in range(2**N):
  cost = 0
  gain = [0 for _ in range(M+1)]
  j = i
  keta = 0
  while j > 0:
    if j & 1:
      cost += A[keta][0]
      for l in range(1,M+1):
        gain[l] += A[keta][l]
        
    j = j >> 1
    keta += 1
    
  result = True
  for l in range(1,M+1):
    if gain[l] < X:
      result = False
      break
    
  if result == True:
    ans = min(ans, cost)
      
print(ans if ans < 10**30 else -1)

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

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

for i in range(2**n):
    total = 0
    r = [0]*m
    flag = True
    for j in range(n):
        if (i>>j) & 1:
            total += C[j] 
            for k in range(m):
                r[k] += A[j][k]
                
    for i in r:
        if i < x:
            flag=False
            break
    
    if flag:
        ans = min(ans,total)
        
if not flag:
    print(-1)
    exit()

print(ans)

Solution (Python):
import itertools
import numpy as np
N, M, X = [int(_) for _ in input().split()]
CA = np.array([[int(_) for _ in input().split()] for _ in range(N)], dtype=int)
ans = 10**10
for bs in itertools.product(range(2), repeat=N):
    s = np.zeros(M + 1, dtype=int)
    for i, b in enumerate(bs):
        if b:
            s += CA[i]
    if np.all(s[1:] >= X):
        ans = min(ans, s[0])
if ans == 10**10:
    print(-1)
else:
    print(ans)

Solution (Python):
from math import inf
n, m, x = map(int, input().split())
ca = list()
for _ in range(n):
    ca.append(list(map(int, input().split())))

money = inf
tmp = 1
for i in range(n):
    tmp += 2**i
for i in range(tmp):
    B = str(format(i, str(n).zfill(n)+'b'))
    j = 0
    cnt = 0
    a = [0]*m
    for ch in B:
        if ch == '1':
            cnt += ca[j][0]
            for k in range(1, m+1):
                a[k-1] += ca[j][k]
        j += 1
    for ch in a:
        if ch < x:
            break
    else:
        money = min(cnt, money)
print(-1 if money == inf else money)

Solution (Python):
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
ans = []
for i in range(2 ** n):
    price = 0
    und = [0 for _ in range(m)]
    for j in range(n):
        if (i >> j) & 1:
            price += c[j][0]
            for k in range(m):
                und[k] += c[j][k+1]
    if all(und[i] >= x for i in range(m)):
        ans.append(price)
 
if ans == []:
    print(-1)
else:
    print(min(ans))

Solution (Python):
n,m,x=map(int,input().split())
a=[]
e=10**8
for i in range(n):
    b=list(map(int,input().split()))
    a.append(b)
for i in range(2**n):
    c=[0]*(m+1)
    s=0
    for j in range(n):
        if i>=2**(n-j-1):
            i-=2**(n-j-1)
            c=[x+y for (x,y) in zip(a[j],c)]
    for j in range(m):
        if c[1+j]<x:
            s+=1
    if s==0 and e>c[0]:
        e=c[0]
if e==100000000:
    print(-1)
else:
    print(e)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
N, M, X = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
ans = 10 ** 10
for i in range(2 ** N):
    p = [0] * M
    sum = 0
    for j in range(N):
        if ((i >> j) & 1):
            sum += li[j][0]
            for k in range(M):
                p[k] += li[j][k + 1]
        if all(x >= X for x in p):
            ans = min(sum, ans)

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

Solution (Python):
import math

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 = math.inf

for i in range(2**N):
    a = [0]*M
    c = 0

    flag = True
    
    for j in range(N):
        if ((i >> j) & 1):
            a = list(map(sum, zip(a, A[j-1])))
            c += C[j-1]

    for x in a:
        if x < X:
            flag = False
            break
    
    if flag:
        ans = min(ans, c)

if ans == math.inf:
    ans = -1

print(ans)