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())

A = []
for i in range(N):
    a = []
    for m in map(int, input().split()):
        a.append(m)
    A.append(a)

min_cost = float("INF")

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            for d in [0, 1]:
                for e in [0, 1]:

                    for f in [0, 1]:
                        for g in [0, 1]:
                            for h in [0, 1]:
                                for i in [0, 1]:
                                    for j in [0, 1]:

                                        for k in [0, 1]:
                                            for l in [0, 1]:

                                                x = {}
                                                for m in range(1, M + 1):
                                                    x[m] = 0
                                                cost = 0
                                                if a == 1 and len(A) >= 1:
                                                    cost += A[0][0]
                                                    for m in range(1, M+1):
                                                        x[m] += A[0][m]
                                                if b == 1 and len(A) >= 2:
                                                    cost += A[1][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[1][m]
                                                if c == 1 and len(A) >= 3:
                                                    cost += A[2][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[2][m]
                                                if d == 1 and len(A) >= 4:
                                                    cost += A[3][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[3][m]
                                                if e == 1 and len(A) >= 5:
                                                    cost += A[4][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[4][m]

                                                if f == 1 and len(A) >= 6:
                                                    cost += A[5][0]
                                                    for m in range(1, M+1):
                                                        x[m] += A[5][m]
                                                if g == 1 and len(A) >= 7:
                                                    cost += A[6][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[6][m]
                                                if h == 1 and len(A) >= 8:
                                                    cost += A[7][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[7][m]
                                                if i == 1 and len(A) >= 9:
                                                    cost += A[8][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[8][m]
                                                if j == 1 and len(A) >= 10:
                                                    cost += A[9][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[9][m]

                                                if k == 1 and len(A) >= 11:
                                                    cost += A[10][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[10][m]
                                                if l == 1 and len(A) >= 12:
                                                    cost += A[11][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[11][m]

                                                success = True
                                                for m in range(1, M + 1):
                                                    if x[m] < X:
                                                        success = False
                                                        break

                                                if success:
                                                    if cost < min_cost:
                                                        min_cost = cost

if min_cost == float("INF"):
    print(-1)
else:
    print(min_cost)

Solution (Python):
import itertools
import numpy as np

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

lis_C = np.array(list(map(lambda x: x[0], lis_all)))
lis_A = np.array(list(map(lambda x: x[1:], lis_all)))

row_idx = []
bools = [True,False]
for boollis in itertools.product(bools, repeat=N):
    row_idx.append(list(boollis))


c_min = lis_C.sum()+100
for i in range(len(row_idx)):
    if all(lis_A[row_idx[i]].sum(axis=0) >= X):
        c_min = min(lis_C[row_idx[i]].sum(), c_min)
if c_min > lis_C.sum():
    ans = -1
else :
    ans = c_min
print(ans)

Solution (Python):
N,M,X = map(int,input().split())
CA = []
for i in range(N):
    CA.append(list(map(int,input().split())))
xx = []    
ans = []
for i in range(2**N):
    ans.append(((bin(i))[2:]).zfill(N))
tmp = [0]*(M+1)
cost = []
for a in ans:
    for i in range(N):
        if a[i] == '0':
            for j in range(M+1):
                tmp[j] += CA[i][j]
    xx.append(tmp)
    tmp = [0]*(M+1)
aa = 0
for L in xx:
    for i in range(1,M+1):
        if L[i] >= X:
            aa += 1
    if aa == M:
        cost.append(L[0])
    aa = 0

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

Solution (Python):
import itertools
import numpy as np
N,M,X=map(int,input().split())
ls = np.array([np.array(list(map(int,input().split()))) for i in range(N)])

mn = -1
for i in range(1,1+N):
  for v in itertools.combinations(ls, i):
    
    ln = len(v)
    ans = 0
    for k in range(ln):
      ans+=v[k]
    
    if np.count_nonzero(ans[1:] >= X) ==M:
      if mn == -1:
        mn = ans[0]
      else:
        mn = min(mn,ans[0])
    
print(mn)

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

import itertools
z = itertools.product([0,1],repeat=n)
t = []
s = []
for i in z:
    t = [0 for k in range(m)]
    cum=0
    for j in range(n):
        if i[j]==1:
            for k in range(m):
                t[k]+=u[j][k+1]
            cum+=u[j][0]
    for b in t:
        if b<x:
            break
    else:
        s.append(cum)
if len(s) !=0:
    print(min(s))
else:
    print(-1)

Solution (Python):
n,m,x = map(int,input().split())
s = [list(map(int,input().split())) for i in range(n)]
s.insert(0,[0]*(m+1))

dp_list = ([0]*m)*(n+1)

ans = 10**7

def dp(i,cost,rikai):
    global ans
    frag = True
    tmp = [j for j in rikai]
    for j in range(m):
        if tmp[j] < x:
            frag = False
    if frag == True:
        ans = min(ans,cost)
        pass
    if i == n:
        if frag == True:
            ans = min(ans,cost)
    else:
        dp(i+1,cost,tmp)
        for j in range(m):
            tmp[j] += s[i+1][j+1]
        dp(i+1,cost+s[i+1][0],tmp)
            

dp(0,0,[0]*m)

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

Solution (Python):
import math

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

tbs = []
for i in range(N):
    arr = list(map(int, input().split()))
    tbs.append(arr)
tbs.reverse()

m = -1
for i in range(2 ** N):
    _sum = [0] * (M + 1)
    for s in range(N):
        bit = (i >> s) & 1
        if bit == 0:
            continue
        for j in range(len(_sum)):
            _sum[j] += tbs[s][j]
    if min(_sum[1:]) < X:
        continue
    if m == -1 or m > _sum[0]:
        m = _sum[0]        

print(m)

Solution (Python):
import itertools

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

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

ans = []
for i in range(n):
    for combination in list(itertools.combinations(range(n), i+1)):
        
        total = 0
        li = [0] * m
        for j in combination:
            total += C[j]
            for k in range(m):
                li[k] += A[j][k]
        flag = True
        for l in range(m):
            if li[l] < x:
                flag = False
        if flag:
            ans.append(total)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Solution (Python):
def hantei(ls, X):
    dekita=True
    for i in ls:
        if i < X:
            dekita=False
    if dekita==True:
        return True
    else:
        return False


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

keihi_rireki=[]
for i in range(2**N):
    rikaido=[0]*M
    keihi=0
    dekita=False
    for j in range(N):
        if((i>>j) & 1):
            keihi=keihi+hon[j][0]
            for k in range(M):
                rikaido[k]=rikaido[k]+hon[j][k+1]
    if hantei(rikaido, X)==True:
        keihi_rireki.append(keihi)

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

Solution (Python):
import numpy as np
N,M,X = map(int,input().split())
shop = []
for i in range(N):
    shop.append(list(map(int,input().split())))

LIST = []
for i in range(2**N):
    L = []
    for j in range(N):
        if((i>>j) & 1):
            L.append(shop[j])
    LIST.append(L)
    
ans = 10**18

for tmp in LIST:
    tmp = np.array(tmp)
    isOK = np.sum(tmp,axis=0)
    dame = False
    if len(tmp)>0:

        for item in isOK[1:]:
            if item < X:
                dame = True
        if dame == False:
            ans = min(ans,isOK[0])
        
if ans==10**18:
    print(-1)
else:
    print(ans)

Solution (Python):
N, M, X = map(int, input().split())
C = [0]*N
S = [0]*N

for i in range(N):
    c, *s = map(int, input().split())
    C[i] = c
    S[i] = list(s)

ans = 10**7
for i in range(2**N):
    num = i
    data = [0]*M
    cost = 0
    for j in range(N):
        if num&1 == 1:
            for k in range(M):
                data[k] += S[j][k]
            cost += C[j]
        num >>= 1
    if min(data) >= X:
        ans = min(ans, cost)

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

Solution (Python):
import sys;input=lambda:sys.stdin.readline().rstrip();aint=lambda:int(input());ints=lambda:list(map(int,input().split()))
import math;floor,ceil=lambda x:int(math.floor(x)),lambda x:int(math.ceil(x))
from functools import reduce;gcd=lambda*x:reduce(math.gcd,x);lcm=lambda*x:reduce(lambda x,y:(x*y)//gcd(x,y),x,1)
import numpy as np
from collections import deque
from itertools import combinations
import bisect
Yes=lambda b:print("Yes"if b else"No");YES=lambda b:print("YES"if b else"NO")
is_even=lambda x:True if x%2==0 else False

def main():
    n,m,x=ints()
    ca=[]
    val=[]
    for _ in range(n):
        inp=ints()
        ca.append(inp)
        flg=1
        for i in range(1,m+1):
            if inp[i]<x:
                flg = 0
        val.append(inp[0]) if flg==1 else None
    for num in range(2,n+1):
        for v in combinations(ca,num):
            vnp = np.array(v)
            s=vnp.sum(axis=0)
            flg=1
            for i in range(1,m+1):
                if s[i]<x:
                    flg = 0
            val.append(s[0]) if flg==1 else None
    
    print(-1 if not val else min(val))

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import numpy as np

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    X = int(next(tokens))  
    A = np.zeros((N,M+1))
    for i in range(N):
        A[i] = [int(next(tokens)) for _ in range(M+1)]
    
    min_c = [10000000]

    def dfs(k, dep):
        if dep == N-1:
            if (k[1:]>=X).all():
                min_c[0] = min(min_c[0], k[0])
            elif ((k+A[dep])[1:]>=X).all():
                min_c[0] = min(min_c[0], k[0]+A[dep][0])
        else:
            dfs(k+A[dep],dep+1)
            dfs(k,dep+1)
    
    dfs(np.zeros(M+1), 0)
    
    if min_c[0] != 10000000:
        print(int(min_c[0]))
    else:
        print(-1)




if __name__ == '__main__':
    main()

Solution (Python):

import itertools
n, m, x = map(int, input().split())
ca = [list(map(int, input().split()))for i in range(n)]
l = []
ans = 1e10
for i in range(1, n+1):
    for j in itertools.combinations(range(n), i):
        
        tmp = 0 
        li = [0] * m
        for k in j:
            
            tmp += ca[k][0]
            for o in range(m):
                
                li[o] += ca[k][o + 1]
        
        count = 0  
        for p in li:
            
            if p >= x:
                count += 1
            else:
                break
        
        if count == m:
            
            ans = min(ans, tmp)
if ans != 1e10:
    print(ans)
else:
    print(-1)

Solution (Python):
import numpy as np
import itertools

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

A = np.array(A)
C = np.array(C)
result = -2
A_sum = A.sum(axis=0)
if A_sum.min() < X:
    result = -1
else:
    n = np.array(list(range(N)))
    money_min = C.sum()
    for i in reversed(n + 1):
        is_enough = False
        comb = itertools.combinations(n, i)
        for _c in comb:
            c = np.array(_c)
            _A = A[c]
            _C = C[c]
            _score = _A.sum(axis=0)
            _money = _C.sum()
            if _score.min() >= X:
                is_enough = True
                if _money < money_min:
                    money_min = _money
        if not is_enough:
            break
    result = money_min
print(result)

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

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

def bit_fullsearch(target):
    n = len(target)
    ret = []
    for i in range(2**n):
        tmp = []
        for j in range(n):
            if (i>>j)&1:
                tmp.append(target[j])
        ret.append(tmp)
    return ret

n,m,x = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
ans = float('inf')

for l in bit_fullsearch(lst):
    tmp = [0 for _ in range(m+1)]
    for k in l:
        for i in range(m+1):
            tmp[i] += k[i]
    if min(tmp[1:]) >= x:
        ans = min(ans, tmp[0])
print(ans if ans!=float('inf') else -1)

Solution (Python):
import numpy as np

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

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

patterns = []
for i in range(2**n):
    tmp = [False] * n
    for j in range(n):
        if ((i >> j) & 1):
            tmp[j] = True
    patterns.append(tmp)

price = []
for pattern in patterns:
    info = np.array([0]*(m+1))
    for i in range(n):
        if (pattern[i] == True):
            l = np.array(books[i])
            info += l
    else:
        if (min(info.tolist()[1:]) >= x):
            price.append(info.tolist()[0])
            
if (len(price) == 0):
    print(-1)
else:
    print(min(price))

Solution (Python):
import itertools

n,m,x=map(int,input().split())
ca=[0]*n
num=[]
ls=[]
last=[]
test=0
ng=0
money=0
for i in range(n):
  ca[i]=input().split()
  num.append(i)
  
for j in range(1,n+1):
  ls=list(itertools.combinations(num,j))
  
  for k in range(len(ls)):
    test=0
    money=0
    ng=0
    for l in range(m):
      test=0
      for p in range(j):
        test+=int(ca[ls[k][p]][l+1])
      if test<x:
        ng+=1
    if ng==0:
      for q in range(j):
        money+=int(ca[ls[k][q]][0])
      last.append(money)

if len(last)>0:
  print(str(min(last)))
else:
  print("-1")

Solution (Python):



import sys
import pprint
import itertools

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, m, x = map(int, sys.stdin.readline().split())
	c = []
	a = []
	for i in range(n):
		ci, *ai = map(int, sys.stdin.readline().split())
		c.append(ci)
		a.append(ai)
	ans = 10**9
	log.print(a)
	for i in range(2**n):
		cost = 0
		rikai = [0]*m
		case = []
		for j in range(n):
			case.append(i>>j & 1)
		for j in range(n):
			if not case[j]:
				continue
			cost += c[j]
			for k in range(m):
				rikai[k] += a[j][k]
		
		if len(list(filter(lambda z:z>=x, rikai))) == m:
			ans = min(cost, ans)
	if ans == 10**9:
		print(-1)
		exit()
	print(ans)





main()

Solution (Python):
import numpy as np
n,m,x = map(int,input().split())
CA = []
money = 10**7

for i in range(n):
  ca = list(map(int,input().split()))
  CA.append(ca)
  
CA = np.array(CA)
for i in range(2**n):
  tmp = 0
  X = np.array([0]*m)
  for j in range(n):
    if (i>>j)&1:
      X += CA[j][1:]
      tmp += CA[j][0]
  N = len([1 for z in X if z>=x])
  if N == m:
    money = min(money,tmp)

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

Solution (Python):
import itertools
import numpy 

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

price = []
tmp = []

for i in range(N):
  _ = list(map(int, input().split()))
  price.append(_[0])
  tmp.extend(_[1:])
price = numpy.array(price)
learn = numpy.array(tmp).reshape((N, M))

if min(numpy.sum(learn, axis=0)) < X:
  print(-1)
else:
  success_combs = []
  for k in range(1, N+1):
    for comb in itertools.combinations(range(N), k):
      if min(numpy.sum(learn[comb, :], axis=0)) >= X:
        success_combs.append(comb)

  min_p = None
  for comb in success_combs:
    p = sum(numpy.take(price,comb))
    if min_p is None:
      min_p = p
    elif min_p > p:
      min_p = p
  print(min_p)

Solution (Python):



from math import *
from copy import *					
from heapq import *					
from string import *				
from random import *				
from bisect import *				
from sys import stdin				
from sys import maxsize				
from operator import *				
from itertools import *				
from collections import Counter		
from collections import defaultdict 

'''
12 5 22
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
'''

def solve(l,n,m,x):
	totPossible = defaultdict(int)
	for j in range(1,m+1):
		for i in range(n):
			totPossible[j] += l[i][j]
	for i in totPossible:
		if(totPossible[i] < x):
			return -1
	combs = []
	for i in range(1,n+1):
		ll = [i for i in range(n)]
		c = list(combinations(ll,i))
		combs.append(c)
	minn = maxsize
	ccc = []
	for i in combs:
		for j in i:
			ccc.append(j)

	for c in ccc:
		ll = [0]*m
		bought = [0]*n
		curr = 0
		for i in c:
			bought[i] = 1
		for i in range(n):
			if(bought[i]):
				for j in range(1,m+1):
					ll[j-1] += l[i][j]
		f = 1
		for i in range(len(ll)):
			if(ll[i] < x):
				f = 0
				break
		if(f):
			for i in range(n):
				if(bought[i]):
					curr += l[i][0]
			minn = min(minn,curr)
	return minn
	

N,M,X = list(map(int, stdin.readline().rstrip().split()))
L = []
for i in range(N):
	l = list(map(int, stdin.readline().rstrip().split()))
	L.append(l)
ans = solve(L,N,M,X)
print(ans)

Solution (Python):
import itertools

def list_add(in1, in2):
   return list(map(sum, zip(in1, in2)))

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

n = [i for i in range(N)]
c_sum = 0
min_sum = 12 * 10e5
for i in range(N):
    flag = 0
    for v in itertools.combinations(n,i+1):
        c_sum = 0
        At = [0] * M
        for j in range(len(v)):
            At = list_add(At, A[v[j]])
            c_sum += C[v[j]]
        overX = [k for k in At if k >= X]
        if len(overX) == M:
            flag = 1
            min_sum = min([min_sum, c_sum])
if flag == 1:
    print(min_sum)
else:
    print(-1)

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

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

ans = 10**7
notFound = True
Nall = 2**N
idx = [0]*N
for num in range(Nall):
    T = num
    for n in range(N):
        idx[n] = T%2
        T = T //2
        
    S = [0]*M
    cost = 0
    for n1 in range(N):
        if idx[n1] == 1:
            a = A[n1]
            cost += A[n1][0]
            for m in range(M):
                S[m] += a[m+1]
            OK = True
            for m in range(M):
                if S[m] < X:
                    OK = False
            if OK:
                ans = min(ans, cost)
                notFound = False
                
                
if notFound:
    print(-1)
else:
    print(ans)

Solution (Python):
import collections
import functools

import sys

input = lambda: sys.stdin.readline()


def cin_int_list():
    return [int(x) for x in input().split()]


def cin_int_iter():
    return (int(x) for x in input().split())


def cin_int():
    return int(input())


def cout_int_iter(a):
    print(' '.join(map(str, a)))


def iota(n, start=0):
    return list(range(start, n))


def cin_digits_list():
    return [ord(x) - ord('0') for x in input()]


def main():
    n, m, x = cin_int_iter()

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

    cnt = collections.Counter()

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

        c[i] = tmp[0]

        for alg, level in enumerate(tmp[1:]):
            a[i][alg] = level

            cnt[alg] += level

    for alg in range(m):
        if cnt[alg] < x:
            print('-1')
            return

    mem = {}

    def search(i, read, levels, cost):
        if all(level >= x for level in levels):
            return cost

        if i == n:
            return float('inf')

        key = (i, read)
        if key in mem:
            return mem[key]

        ret = min(
            search(i + 1, read | 1 << i, [levels[j] + a[i][j] for j in range(m)], cost + c[i]),
            search(i + 1, read, levels, cost)
        )

        mem[key] = ret

        return ret

    print(search(0, 0, [0 for i in range(m)], 0))


main()

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

import itertools

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

dp_c_a = [[0 for i in range(m+1)] for j in range(len(on_off_list))]


for i in range(len(on_off_list)):
    for j in range(len(on_off_list[i])):
        for k in range(m+1):
            dp_c_a[i][k] +=  c_a_list[j][k] * on_off_list[i][j]

ans_min = 1000000000
for i in range(len(dp_c_a)):
    count = 0
    for j in range(1, len(dp_c_a[i])):
        if dp_c_a[i][j] < x:
            count += 1
    if count == 0:
        ans_min = min(ans_min, dp_c_a[i][0])

if ans_min == 1000000000:
    print(-1)
else:
    print(ans_min)

Solution (Python):
N,M,X=map(int,input().strip().split())
C=[]
A=[]
for n in range(N):
    l=list(map(int,input().strip().split()))
    C.append(l[0])
    A.append(l[1:])

cost=sum(C)
reach=False
def dfs(L,N):
    global reach
    global cost
    if len(L)==N:
        skill=[0 for m in range(M)]
        temp=0
        for n in range(N):
            if L[n]==1:
                temp+=C[n]
                for m in range(M):
                    skill[m]+=A[n][m]
        res=True
        for e in skill:
            if e<X:
                res=False
                break
        
        if res==True:
            reach=True
            if temp<=cost:
                cost=temp     
        return
    
    else:
        for i in range(2):
            L.append(i)
            dfs(L,N)
            L.pop()

dfs([],N)
if reach==True:
    print(cost)
else:
    print(-1)

Solution (Python):
import numpy as np
import itertools
import math
n, m, x = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(n)] 
CA = np.array(CA)
C = CA[:, 0]
A = CA[:, 1:]
B = np.array([x]*m)

combs = itertools.product(range(2), repeat=n)
opt_val = math.inf
for com in combs:
    X = np.array(com)
    if np.all(A.T @ X >= B):
        opt_val = min(C @ X, opt_val)
if opt_val == math.inf:
    print('-1')
else:
    print(opt_val)

Solution (Python):
import copy
n,m,x = map(int,input().split())
ca = [0]*n
for i in range(n):
    ca[i] = list(map(int,input().split()))
ans = 10**8

for i in range(1 << n):
    sum = 0
    result = [0]*m
    for j in range(n):
        if (i >> j) & 1 == 1:
            for k in range(m):
                result[k] += ca[j][k+1]
            sum += ca[j][0]
    if min(result) >= x and ans > sum:
        ans = copy.deepcopy(sum)

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

Solution (Python):
import numpy as np

N,M,X = map(int, input().split())
books = []
for i in range(N):
    book = list(map(int, input().split()))
    books.append(book)
books = np.array(books)
answer = 10**5 * N
for i in range(2**N):
    flag = False
    bin_str = format(i, '0{}b'.format(N))
    bin_array = []
    for letter in bin_str:
        bin_array.append(int(letter))
    bin_array = np.array(bin_array).reshape(N,1)
    v = np.sum(bin_array*books, axis=0)
    
    j = 0
    while j < M:
        if v[j+1] < X:
            break
        j += 1
        if j == M:
            flag = True
            answer = min(answer, v[0])
if flag:
    print(answer)
else:
    print('-1')

Solution (Python):
import itertools

def main():
    n,m,x = map(int,input().split())
    c = [[0] * (m+1)]*n
    sum_l = [0]*m
    min_money = 100000000
    money = 0
    cnt = 0
    t = 0

    result  = []

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

    for i in range(1,n+1):
        for conb in itertools.combinations(list(range(n)),i):
            result.append(list(conb))
            cnt += 1

    
    
    for i in range(cnt):
        for j in range(len(result[i])):
            for k in range(m):
                sum_l[k] += c[result[i][j]][k+1]
            money += c[result[i][j]][0]

            for k in range(m):
                if sum_l[k] >= x:
                    t += 1
            if t == m:
                if min_money > money:
                    min_money = money
            t = 0
        
        sum_l = [0]*m
        money = 0

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

    
if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*(M+1))
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 10000000000
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
      break
  if t == 0:
    min_price = min(min_price, i[0])
 
if min_price == 10000000000:
  print(-1)
else:
  print(min_price)

Solution (Python):
nmx = [int(x) for x in input().split()]
n = nmx[0]
m = nmx[1]
x = nmx[2]

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


def dp(i, cost, scores):
    if i == n:
        ok = True
        for j in range(0, m):
            if scores[j] < x:
                ok = False
        if ok == True:
            return(cost)
        else:
            return(999999999999)
    else:
        newCost = cost + lis[i][0]
        newScores = [0]*m
        for j in range(0,m):
            newScores[j] = scores[j] + lis[i][j+1]
        return(min([dp(i+1,cost,scores), dp(i+1,newCost,newScores)]))

temp = [0]*m

yeet = (dp(0,0,temp))
if yeet == 999999999999:
    print(-1)
else:
    print(yeet)

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

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


index=[]
for i in range(n):
    index.append(i)
patarns=[]
for i in range(1,n+1):
    patarns.append(itertools.combinations(index,i))
    


for patarn in patarns:
    
    
    for bk_indexies in patarn:
        
        flg=True
        for arg in range(m):
            point=0
            money=0
            for bk_index in bk_indexies:
                
                point+=books[bk_index][arg+1]
                money+=books[bk_index][0]
            
            if point<x:
                flg=False
        if flg:
            
            results.append(money)

print(min(results))