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())
C = []
A = []
for i in range(N):
    ls = list(map(int,input().split()))
    C.append(ls[0])
    A.append(ls[1:])

INF = 10**9
ans = INF
for i in range(2**N):
    skill = [0]*M
    yen = 0
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                skill[k] += A[j][k]
            yen += C[j]
    ok = True
    for j in skill:
        if j < X:
            ok = False

    if ok:
        ans = min(ans,yen)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from sys import stdin
import itertools

n, m, x = [int(x) for x in stdin.readline().rstrip().split()]
c = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
c.sort()
mi = -1
r = 0

for j in range(1, m + 1):
    li = [x[j] for x in c]
    li.sort(reverse=True)
    for i in range(1, len(li) + 1):
        if sum(li[:i]) >= x:
            r = max(r, i)
            break

for h in range(r, n + 1):
    for i in itertools.combinations(c, h):
        cnt = [0] * m
        mon = 0
        for j in i:
            cnt = [cnt[k]+j[k+1] for k in range(len(cnt))]
            mon += j[0]
            if sum(1 for k in cnt if k >= x) == m:
                if mi > mon or mi == -1:

                    mi = mon
                break

print(mi)

Solution (Python):
def main():
    import itertools
    N, M, X = map(int, input().split())
    
    
    dict = {}
    c_dict = {}
    a_dict = {}
    count = 0
    count_list = []
    for i in range(1,N+1) :
        count = count + 1
        count_list.append(count)
        A_list = [A for A in input().split()]
        A_list = list(map(int, A_list))
        
        
        dict[A_list[0]] = A_list[1:]
        c_dict[count] = A_list[0]
        a_dict[count] = A_list[1:]

    comb_lists = []
    for i in range(1, len(count_list)+1) :
        for comb_list in itertools.combinations(count_list, i) :
            comb_lists.append(list(comb_list))
    
    result = -1
    for key_list in comb_lists :
        ans = 0
        t = [0] * M
        
        for key in key_list :
            ans = ans + c_dict[key]
            
            for j in range(M) :
                t[j] = t[j] + a_dict[key][j]
        
        if all(x >= X for x in t) :
            if result == -1 :
                result = ans
            else :
                result = min(result, ans)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
n, m, k = [int(x) for x in input().split()]
li = [[int(x) for x in input().split()] for _ in range(n)]
prices = []
for bit in range(1, 2 ** n):
    index_list = []
    for i in range(n):
        if bit & 1 << i:
            index_list.append(i)
    c = 0
    for t in range(1, m + 1)        :
        s = 0
        for i in index_list:
            s += li[i][t]
        if s >= k:
            c += 1
        else:
            break
    if c == m:
        p = 0
        for i in index_list:
            p += li[i][0]
        prices.append(p)
if prices:
    print(min(prices))
else:
    print(-1)

Solution (Python):

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

MOD = 10**9+7
a = [0]*M
value = [0]
ans = MOD

for i in range(2**N):
    for j in range(N+1):
        if(i >> j) & 1:
            for k in range(M):
                a[k] += A[j][k+1]
            value.append(A[j][0])

    if min(a) >= X :
        ans = min(ans,sum(value))
    a = [0]*M
    value = []

print(-1 if ans == MOD else ans)

Solution (Python):


def saiki(count,price,lis):
    if count==N:
        judge=True
        for item in lis:
            if item<X:
                judge=False
        if judge:
            ans.append(price)
    else:
        temp=[lis[i]+note[count][i+1] for i in range(M)]
        saiki(count+1,price,lis)
        saiki(count+1,price+note[count][0],temp)

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

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

ans=[]
saiki(0,0,[0]*M)

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

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

'''
n,m,x = [int(i) for i in input().split()]
costs =[]

for i in range(n):
    a = [int(i) for i in input().split()]
    costs.append(a)
'''


INF = 1000000000000000000000000000
ans = INF

for i in range(1<<n):  
    
    c = 0
    sums = [0]*m
    for j in range(n):
        if i>>j & 1: 
            
            c += costs[j][0]
            for k in range(m):
                sums[k] += costs[j][k+1]    
    '''
    cost = 0
    c = 0
    sums = [0] * m
    use_index=[]
    for j in range(n):
        if i%2==1:
            use_index.append(j)
        i >>= 1
    
    for v in use_index:
        c += costs[v][0]        
        for j in range(m):
            sums[j] += costs[v][j+1]
    '''
    
    if min(sums) >= x:
        ans = min(ans, c)
'''            
    judge=True
    for j in range(m):
        if sums[j]<x:
            judge=False
            break
    
    if judge:
        ans = min(ans, c)
'''
if ans==INF:
    print(-1)
else:
    print(ans)

Solution (Python):
n, m, k = map(int, input().split())
li = []
for t in range(n):
    li.append(list(map(int, input().split())))
price_list = []
for bit in range(1, 2**n):
    index_list = []
    for i in range(n):
        if bit & 1<<i:
            index_list.append(i)

    c = 0
    for t in range(1,m+1):
        s = 0
        for i in index_list:
            s += li[i][t]
        if s >= k:
            c += 1
        else:
            break

    if c == m:
        p = 0
        for i in index_list:
            p += li[i][0]
        price_list.append(p)

if len(price_list):
    print(min(price_list))
else:
    print('-1')

Solution (Python):
n, m, k = map(int, input().split())
li = []
for t in range(n):
    li.append(list(map(int, input().split())))
price_list = []
for bit in range(1, 2**n):
    index_list = []
    for i in range(n):
        if bit & 1<<i:
            index_list.append(i)

    c = 0
    for t in range(1,m+1):
        s = 0
        for i in index_list:
            s += li[i][t]
        if s >= k:
            c += 1

    if c == m:
        p = 0
        for i in index_list:
            p += li[i][0]
        price_list.append(p)

if len(price_list):
    print(min(price_list))
else:
    print('-1')

Solution (Python):
Books,Cost,X=None,None,None
DP={}

def getUnderstanding(prev,curr):
    global Books
    L=[]
    for i in range(len(prev)):
        L.append(prev[i]+Books[curr][i])
    return L
def isUnderstandingReached(prev):
    global X
    for u in prev:
        if u<X:
            return False
    return True

def F(curr,prev):
    global Books,Cost,X,DP
    
    
    if isUnderstandingReached(prev):
        return 0
    if curr==len(Books):
        return float('inf')
    DP[(curr,tuple(prev))]=min(Cost[curr]+F(curr+1,getUnderstanding(prev,curr)),F(curr+1,prev))
    return DP[(curr,tuple(prev))]

N,M,X=map(int,input().strip().split())
Books=[]
Cost=[]
for i in range(N):
    L=list(map(int,input().strip().split()))
    Books.append(L[1:])
    Cost.append(L[0])
res=F(0,[0]*len(Books[0]))
if res==float('inf'):
    print(-1)
else:
    print(res)

Solution (Python):
from copy import deepcopy
INF = 1001001001
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    k = list(map(int, input().split()))
    C.append(k[0])
    A.append(deepcopy(k[1:]))

ans = INF
for s in range(1 << N):
    cost = 0
    d = [0]*M
    for i in range(N):
        if s >> i & 1:
            cost += C[i]
            for j in range(M):
                d[j] += A[i][j]
    ok = True
    for j in range(M):
        if d[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost)

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

Solution (Python):
n,m,x=map(int,input().split())
item=[list(map(int,input().split()))for i in range(n)]
bag=[]
for i in range(2**n):
    temp=[]
    job=[0]*m
    for s in range(n):
        if (i>>s)&1:
            temp.append(s)
            for y in range(m):
                job[y]+=item[s][y+1]
    for s in range(len(job)):
        if job[s]<x:
            break
    else:
        money=0
        for s in temp:
            money+=item[s][0]
        bag.append(money)

print(min(bag) if len(bag)>=1 else -1)

Solution (Python):
import sys

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, M, X = IL()
	c = [0] * N
	a = [[0] * M for _ in range(N)]
	for i in range(N):
		tmp = IL()
		c[i] = tmp[0]
		a[i][:] = tmp[1:]

	min_price = sys.maxsize
	for i in range(2**N):
		sum_price = 0
		rikaido = [0] * M
		for j in range(N):
			if (i>>j) & 1:
				sum_price += c[j]
				for k in range(M):
					rikaido[k] += a[j][k]
		if min(rikaido) >= X:
			min_price = min(min_price, sum_price)
	
	if min_price == sys.maxsize:
		print(-1)
	else:
		print(min_price)



if __name__ == "__main__":
	main()

Solution (Python):


n,m,x=map(int,input().split())
item=[list(map(int,input().split()))for i in range(n)]
book=[i for i in range(n)]
bag=[]
for i in range(2**n):
    temp=[]
    job=[0]*m
    for s in range(n):
        if (i>>s)&1:
            temp.append(s)
            for y in range(m):
                job[y]+=item[s][y+1]
    for s in range(len(job)):
        if job[s]<x:
            break
    else:
        money=0
        for s in temp:
            money+=item[s][0]
        bag.append(money)

print(min(bag) if len(bag)>=1 else -1)

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

ans = float('inf')
for i in range(1<<N):
  tmp = [0]*(M+1)
  for j in range(N):
    if i&(1<<j)==0: continue
    for k,l in enumerate(A[j]):
      tmp[k] += l
  if all(e>=X for e in tmp[1:]):
    ans = min(ans, tmp[0])
if ans==float('inf'):
  ans = -1
print(ans)

Solution (Python):
import numpy as np
import itertools

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

As = []

for i in range(N) :
  As.append(list(map(int, input().split())))
  
L_As = len(As[0])
cal = np.zeros(L_As)
ans = []
for j in range(1, N+1) :
  for k in itertools.combinations(As, j) :
    for l in k :
      cal = cal + np.array(l)
    if min(cal[1:L_As]) >= X :
      ans.append(cal[0])
    cal = np.zeros(len(As[0]))

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

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

books = []
for i in range(n):
	book = list(map(int, input().split()))
	books.append(book)
    
ans = float('inf')
for s in range(1 << n):
  cost = 0
  d = [0] * m
  for i in range(n):
    if (s >> i & 1):
      cost += books[i][0]
      for j in range(m):
        d[j] += books[i][j+1]
  ok = True
  for j in range(m):
    if(d[j] < x):
      ok = False
  if ok:
    ans = min(cost, ans)
if (ans == float('inf')):
  print("-1")
else :
  print(ans)

Solution (Python):

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



price_list=[]
cl=[]
al=[]
for i in range(n):
    l=list(map(int,input().split()))
    cl.append(l[0])
    al.append(l[1:])


for i in range(2**n):
    b=bin(i)
    price=0
    score=[0 for k in range(m)]
    
    
    for j in range(n):
        if ((i >> j) & 1):
            a=al[j]
            for k in range(m):
                score[k]=score[k]+a[k]
            price+=cl[j]
    
    if min(score)>=x:
        price_list.append(price)

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

Solution (Python):
INF = 1e10

N, M, X = map(int, input().split())
C, A = [], []
for i in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)

ans = INF

for s in range(1<<N):
    cost = 0
    d = [0]*M
    for i in range(N):
        if s>>i&1:
            cost += C[i]
            for j in range(M): d[j] += A[i][j]

    ok = True
    for j in range(M):
        if d[j] < X: ok = False
    if ok: ans = min(ans, cost)

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

Solution (Python):


def loop(n_cnt, my_list):
    if n_cnt==n:     
        bool_list = [i>=x for i in my_list[1:]]
        if all(bool_list):
            ans.append(my_list[0])
    else:
        
        add_list = [my_list[i] + CA[n_cnt][i] for i in range(m+1)]
        loop(n_cnt+1, my_list)
        loop(n_cnt+1, add_list)
        

n,m,x = map(int,input().split())
CA = [list(map(int,input().split())) for _ in range(n)]

ans = []

loop(0,[0]*(m+1))
print(min(ans) if len(ans)!=0 else '-1')

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

a = [[0 for i2 in range(12)] for i1 in range(12)]
c=[0]*N
for i in range(N):
    C=list(map(int,input().split()))
    c[i]=C[0]
    for j in range(M):
        a[i][j]=C[j+1]

INF=1200001
ans=INF

for s in range(1<<N):
    cost = 0
    d = [0]*M
    for i in range(N):
        if(s>>i&1):
            cost+=c[i]
            for j in range(M):
                d[j]+=a[i][j];
    ok=1
    for j in range(M):
        if d[j]<X:
            ok=0
    if(ok):
        ans=min(ans,cost)
if(ans==INF):
    print(-1)
else:
    print(ans)

Solution (Python):
import itertools
import numpy as np

N, M, X = map(int, input().split())
items = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int32)

out = 10**18
for c in itertools.product([False, True], repeat=N):
    tmp = np.sum(items[np.where(c)], axis=0)
    if M == np.count_nonzero(tmp[1:] >= X):
      out = min(out, tmp[0])

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

Solution (Python):
def main():
    N, M, X = [int(x) for x in input().split()]
    Cl, All = [], []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        Cl.append(tmp[0])
        All.append((tmp[1:]))
    
    min_cost = sum(Cl) + 1
    
    for bit in range(1, 1 << N):
        cost = 0
        
        totalAl = [0]*M
        for i, al in enumerate(All):
            
            if (1 << i) & bit:
                for j, a in enumerate(al):
                    totalAl[j] += a
                cost += Cl[i]
        
        check = True
        for a in totalAl:
            if a < X:
                check = False
        if check:
            min_cost = min(min_cost, cost)
    
    if min_cost > sum(Cl):
        print(-1)
    else:
        print(min_cost)


if __name__ == '__main__':
    main()

Solution (Python):
def dfs(i, und, cost, cost_list):
    if i == n:
        for val in und:
            if val < x: break
        else:
            cost_list.append(cost)
        return

    dfs(i + 1, [x + y for x, y in zip(und, a[i])], cost + c[i], cost_list)
    dfs(i + 1, und, cost, cost_list)

    return min(cost_list) if cost_list else -1

n, m, x = map(int,input().split())
c, a = [0] * n, []
for i in range(n):
    c[i], *ai = map(int,input().split())
    a.append(ai)

rec = dfs(0, [0] * n, 0, [])
print(rec)

Solution (Python):
import numpy as np

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

data = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

data_all = []
c_min = INF

for i in range(2**N):
    data_tmp = [0]*M
    c = 0
    for j in range(N):
        if((i>>j) & 1):
            for k in range(M):
                data_tmp[k] += data[j][k+1]
            c += data[j][0]
    if(min(data_tmp) >= X):
        c_min = min(c, c_min)

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

Solution (Python):
import numpy as np

n,m,x = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(n)])
c = arr.T[0]
a = arr.T[1:].T

ans = np.inf
for i in range(2**n):
    ability = np.zeros(m, np.int64)
    cost = 0
    for j in range(n):
        if (i>>j)&1: ability += a[j] ; cost += c[j]
    if np.all(ability>=x): ans = min(ans,cost)

ans = -1 if ans==np.inf else ans
print(ans)

Solution (Python):
import numpy as np

n,m,x = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(n)])
c = arr.T[0] 
a = arr.T[1:].T 

ans = np.inf
for i in range(2**n):
    ability = np.zeros(m, np.int64)
    cost = 0
    
    for j in range(n):
    
        if (i>>j)&1: ability += a[j] ; cost += c[j]
    
    if np.all(ability>=x): ans = min(ans,cost)


ans = -1 if ans==np.inf else ans
print(ans)

Solution (Python):
import numpy as np
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
ans=1e15
for i in range(1<<N):
    B = [0]*M
    C = 0
    for j in range(N):
        if i%2:
            B = [x + y for (x, y) in zip(A[j][1:], B)]
            C += A[j][0]
        i = i//2
    if all(B[i]>=X for i in range(M)):
        ans=min(ans,C)
if ans>=1e15:
    print(-1)
else:
    print(ans)

Solution (Python):

n,m,x=list(map(int,input().split()))
a=[[] for _ in range(n)]
c=[]
ans =10000000
for i in range(n):
	tmp=input().split()
	c.append(int(tmp[0]))
	a[i]=list(map(int,tmp[1:]))
money_req=[0 for _ in range(1<<n)]
subs_know=[[0 for i in range(m)] for _ in range(1<<n)]	
for  i in range(1<<n):
	for j in range(n):
		if(not((1<<j)&i)):
			money_req[(1<<j)|i]=money_req[i] + c[j]
			flag=0
			for k in range(m):
				subs_know[i|1<<j][k]=subs_know[i][k] + a[j][k]
				if(subs_know[i|1<<j][k]<x): flag=1
			if not flag:ans=min(money_req[1<<j|i],ans);	
if ans==10000000: print(-1)
else: print(ans)

Solution (Python):
import numpy as np
import sys

n,m,x = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(n)])

c = arr.T[0] 
a = arr.T[1:].T 


ans = np.inf
for i in range(2**n):
    ability = np.zeros(m, np.int64)
    cost = 0
    for j in range(n):
        if (i>>j)&1: ability += a[j] ; cost += c[j]
    
    if all(i>=x for i in ability): ans = min(ans,cost)

ans = -1 if ans==np.inf else ans
print(ans)

Solution (Python):
n,m,x = map(int,input().split())
books = []
cost = []
min_cost = -1
for _ in range(n):
  ca = [int(x) for x in input().split()]
  cost.append(ca[0])
  books.append(ca[1:])
pset = 2**n
for i in range(1,pset):
  indexes = []
  index = 0
  while i!=0:
    if i&1 == 1:
      indexes.append(index)
    index+=1
    i = i//2
  tot_cost = cost[indexes[0]]
  skill = books[indexes[0]].copy()
  for idx in indexes[1:]:
    tot_cost += cost[idx]
    for j in range(m):
      skill[j] += books[idx][j]
  satisfied = True
  for j in range(m):
    if skill[j] < x:
      satisfied = False
      break
  if satisfied:
    if min_cost==-1:
      min_cost = tot_cost
    else:
      min_cost = min(min_cost,tot_cost)
print(min_cost)

Solution (Python):
import numpy as np

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

B = []
beta = []
for n in range(2**N):
  b = bin(n)[2:].zfill(N)
  beta = []
  for i in range(N):
    beta.append(int(b[i]))
  B.append(beta)
B = np.array(B)

S = np.dot(B,A)
L = []
for n in range(2**N):
  if min(S[n]) >= X:
    L.append(n)
    
if len(L) == 0:
  print(-1)
else:
  kane = []
  for k in range(len(L)):
    kane.append(np.dot(B[L[k]],C))
  print(min(kane))

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

Solution (Python):
def dfs(i, cost, skills):
    if i == N:
        if min(skills) < X:
            return INF
        else:
            return cost
    new_skills = [a + s for a, s in zip(contents[i], skills)]
    return min(dfs(i + 1, cost, skills), dfs(i + 1, cost + prices[i], new_skills))


INF = float('inf')
N, M, X = map(int, input().split())
prices = []
contents = []
for _ in range(N):
    C, *A = map(int, input().split())
    prices.append(C)
    contents.append(A)
if (ans := dfs(0, 0, [0] * M)) == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
n, m, x = map(int, input().split())
b = [list(map(int, input().split())) for _ in range(n)]
ans = 100000000
for i in range(1<<n):
	res = 0
	s = [0 for _ in range(m)]
	for j in range(n):
		if (i>>j)&1:
			res += b[j][0]
			for k in range(1, m+1):
				s[k-1] += b[j][k]
	if min(s) >= x:
		ans = min(ans, res)
if ans != 100000000:
	print(ans)
else:
	print(-1)

Solution (Python):
def dfs(i, cost, skills):
    if i == N:
        if min(skills) < X:
            return INF
        else:
            return cost
    new_skills = [a + s for a, s in zip(contents[i], skills)]
    return min(dfs(i + 1, cost, skills), dfs(i + 1, cost + prices[i], new_skills))


INF = float('inf')
N, M, X = map(int, input().split())
prices = []
contents = []
for _ in range(N):
    C, *A = map(int, input().split())
    prices.append(C)
    contents.append(A)
ans = dfs(0, 0, [0] * M)
if ans == INF:
    print(-1)
else:
    print(ans)

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

A = [[] for _ in range(n)]
c = [0] * n

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

INF = 10**9
ans = INF
    
for s in range(0, 1 << n):
    smart = [0] * m
    cost_sum = 0
    for i in range(n):
        if (s >> i) % 2 == 0:continue
        cost_sum += c[i]
        for j in range(m):
            smart[j] += A[i][j]
    ok = True
    for j in range(m):
        if smart[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost_sum)

if ans == INF:
    ans = -1

print(ans)

Solution (Python):
import itertools

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

ans = -1

for i in range(N):
    for choices in itertools.combinations(range(N), i + 1):
        cost = 0
        a = [0] * M
        for choice in choices:
            cost += books[choice][0]
            for j in range(M):
                a[j] += books[choice][j + 1]

        if min(a) >= X:
            ans = min(cost, ans) if ans >= 0 else cost

print(ans)

Solution (Python):
N, M, X = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
ans = float('inf')

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

    idx = 0
    while i:
        if i % 2:
            a += A[idx][0]
            
            for j in range(1, M+1):
                c[j-1] += A[idx][j]
        
        i //= 2
        idx += 1
        
    f = True
    
    for cc in c:
        if cc < X:
            f = False
            break
    if f: ans = min(ans, a)
    
if ans == float('inf'): ans = -1
print(ans)

Solution (Python):
n, m, x = map(int, input().split())
C = []
A = []
for _ in range(n):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
ans = float("inf")
for i in range(2**n):
    res = 0
    D = [0]*m
    for j in range(n):
        if i >> j & 1:
            res += C[j]
            for k, a in enumerate(A[j]):
                D[k] += a
    for d in D:
        if d < x:
            break
    else:
        ans = min(ans, res)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

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

ans = -1

for bits in range(1 << N):
    cost = 0
    a = [0] * M
    for i in range(N):
        if (bits >> i) & 1 == 1:
            cost += books[i][0]
            for j in range(M):
                a[j] += books[i][j + 1]

    if min(a) >= X:
        ans = min(cost, ans) if ans >= 0 else cost

print(ans)

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

INF = float('inf')


def calc(index, cost, point):
    if index == N:
        if len(list(filter(lambda p: p < X, point))) > 0:
            return INF
        return cost

    np = point[:]
    for i, a in enumerate(book[index][1:]):
        np[i] += a

    return min(calc(index + 1, cost, point), calc(index + 1, cost + book[index][0], np))


res = calc(0, 0, [0 for _ in range(M)])
print(res if res != INF else -1)

Solution (Python):
INF=100100100

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:])
cost=INF
for i in range(2**n):
    ab=[0]*m
    tmp=0
    for j in range(n):
        idx=i>>j & 1
        if(idx):
            tmp+=c[j]
            for k in range(m):
                ab[k]+=a[j][k]
    for k in range(m):
        if(ab[k]<x):break
    else:cost=min(cost,tmp)
if(INF==cost):print(-1)
else:print(cost)

Solution (Python):
import itertools

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

resultMoneyArray = []

for c in itertools.product([False, True], repeat=N):
  tmpMoney = 0
  m_array = [X for i in range(M)]
  for j in range(N):
    if c[j]:
      for k in range(M):
        m_array[k] -= ca_array[j][k+1]
      tmpMoney += ca_array[j][0]
      
  if sum(x > 0 for x in m_array) == 0:
    resultMoneyArray.append(tmpMoney)

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

Solution (Python):




def main():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split()))for _ in range(N)]

    result = []
    for i in range(2**N):
        bins = format(i, "b").zfill(N)
        tmp = [0] * (M + 1)

        for b, ca in zip(bins, CA):
            if b == "1":
                for j in range(M + 1):
                    tmp[j] += ca[j]
        if all([True if k >= X else False for k in tmp[1:]]):
            result.append(tmp)

    if result == []:
        print(-1)
    else:
        print(min([r[0]for r in result]))


if __name__ == "__main__":
    main()

Solution (Python):

def my_loop(n_counter, my_list):
    if n_counter == N:
        bool_list = [i >= X for i in my_list[1:]]
        if all(bool_list):
            ans.append(my_list[0])
    else:
        
        add_list = [my_list[i] + temp[n_counter][i] for i in range(M+1)]
        my_loop(n_counter+1, my_list)
        my_loop(n_counter+1, add_list)


N, M, X = map(int, input().split())
temp = []
ans = []
for _ in range(N):
    temp.append(list(map(int, input().split())))

my_loop(0, [0]*(M+1))
print(min(ans) if len(ans) != 0 else '-1')

Solution (Python):
n,m,x=map(int,input().split())
lis=[list(map(int,input().split())) for i in range(n)]
payment=1e10
flag=True
for i in range(2**n):
    total=0
    skil=[0]*m
    for j in range(n):
        if ((i >> j) & 1):
            total+=lis[j][0]
            for h in range(1,m+1):
                skil[h-1]+=lis[j][h]
    for k in skil:
        if k>=x:
            pass
        else:
            break
    else:
        if payment>total:
            payment=total
if payment==1e10:
    print(-1)
else:
    print(payment)

Solution (Python):
N, M, X = map(int, input().split())
book_list = []
cost = [0] * (2 ** N)

cost_parform = []
for i in range(N):
    book_list.append(list(map(int, input().split())))
for i in range(2 ** N):
    bag = []
    rikaido = [0] * M
    for j in range(N):  
        if (i >> j & 1):
            bag.append(j)
    for k in bag:
        
        
        cost[i] = cost[i] + book_list[k][0]
        for m in range(M):
            rikaido[m] = rikaido[m] + book_list[k][m+1]

    count = 0
    for m in range(M):
        if rikaido[m] >= X:
            count += 1
    if count == M:
        cost_parform.append(cost[i])

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

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

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

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

Solution (Python):
n,m,x = map(int, input().split())
import numpy as np
C = np.array([0]*n)
A = np.array([[0]*m]*n)
for i in range(n):
    l = list(map(int, input().split()))
    C[i] += l[0]
    A[i] += np.array(l[1:])

def L(i):
    X = []
    for j in range(n):
        X.append(i%2)
        i = i//2
    X.reverse() 
    return np.array(X)

ans = []
for k in range(2**n):
    D = np.dot(L(k), A)
    if min(D) >= x:
        ans.append(np.dot(C, L(k)))
        
if ans == []:
    print(-1)
else:
    print(min(ans))

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    ans = float('INF')
    n, m, x = map(int, input().split())
    c = [0]*n
    a = [[0 for _ in range(m)]for _ in range(n)]
    for i in range(n):
        temp = list(map(int, input().split()))
        c[i] = temp[0]
        for j in range(m):
            a[i][j] = temp[j+1]
    for bit in range(1<<n):
        acquired = True
        cost = 0
        d = [0]*m
        for i in range(n):
            if (bit & (1 << i)):
                cost += c[i]
                for j in range(m):
                    d[j] += a[i][j]
        for k in range(m):
            if d[k] < x:
                acquired = False
        if acquired:
            ans = min(ans, cost)
    if ans == float('INF'):
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, m, x = map(int, input().split())
c = []
a = []
INF = 1001001001

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

ans = INF

for s in range(2 ** n):
    cost = 0
    d = [0 for i in range(m)]
    for i in range(n):
        if (s >> i) & 1:
            cost += c[i]
            for j in range(m):
                d[j] += a[i][j]
    ok = True
    for j in range(m):
        if d[j] < x: ok = False
    if ok: ans = min(ans, cost)

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