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):
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,x=n1()
ca=n3(n)
ans=9999999999

import itertools
book=list(itertools.product([0,1], repeat=n))
price=[]
for line in book:
    p=0
    for i in range(n):
        if line[i]==1:
            p+=ca[i][0]
            
    price.append(p)
for i in range(len(book)):
    t=book[i]
    s=[0]*m
    for j in range(n):
        if t[j]==1:
            s=[s[k]+ca[j][k+1] for k in range(m)]
    if len([y for y in s if y>=x])==m:
        ans=min(ans,price[i])
if ans==9999999999:
    print(-1)
else:
    print(ans)

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

def main():
    n,m,x=map(int,input().split())
    C=[]
    As=[]
    for _ in range(n):
        c,*A=map(int,input().split())
        C.append(c)
        As.append(A)
    ans=float('inf')
    for i in range(1<<n):
        S=[0]*m
        tmp=0
        for j,(c,A) in enumerate(zip(C,As)):
            if (i>>j)&1==0:
                continue
            tmp+=c
            for k,a in enumerate(A):
                S[k]+=a
        if min(S)>=x:
            ans=min(ans,tmp)
    print(-1 if ans==float('inf') else ans)
    
if __name__=='__main__':
    main()

Solution (Python):

import itertools
import sys
import numpy as np
INF = float("inf")
N, M, X = list(map(int, sys.stdin.buffer.readline().split()))
A = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
 
A = np.array(A, dtype=int)
mat = A[:, 1:]
C = A[:, 0]
 
ans = INF
for choices in itertools.product((True, False), repeat=N):
    choices = np.array(list(choices), dtype=bool)
    if np.all(mat[choices, :].sum(axis=0) >= X):
        ans = min(ans, C[choices].sum())
if ans == INF:
    print(-1)
else:
    print(ans)

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

flag1 = True
ans = -1

for i in range(1, n + 1):
    if i == 1:
        for j in range(n):
            flag = True
            for k in range(m):
                if T[j][k + 1] < x:
                    flag = False
                    break

            if flag == True and flag1 == True:
                ans = T[j][0]
                flag1 = False
            elif flag == True:
                ans = min(ans, T[j][0])

    else:
        tmp = list(itertools.combinations(range(1, n + 1), i))
        for j in range(len(tmp)):
            flag = True
            M = [0] * m
            tmp1 = 0
            for k in range(len(tmp[j])):
                for l in range(m):
                    M[l] = M[l] + T[tmp[j][k] - 1][l + 1]
                tmp1 = tmp1 + T[tmp[j][k] - 1][0]

            for k in range(m):
                if M[k] < x:
                    flag = False
                    break

            if flag == True and flag1 == True:
                ans = tmp1
                flag1 = False
            elif flag == True:
                ans = min(ans, tmp1)

print(ans)

Solution (Python):
import itertools
n,m,x=list(map(int,input().split()))
ans=10**18
A=[list(map(int,input().split())) for i in range(n)]
for i, _ in enumerate(A,1):
  for j in itertools.combinations(A,r=i):
    B=list(zip(*j))    
    C=[sum(B[m]) for m in range(m+1)]
    if len([i for i in C[1:] if i>=x ])==m:
      ans=min(ans,C[0])
print(ans) if ans!=10**18 else print(-1)

Solution (Python):
N, M, X = map(int,input().split())
a=[]
b=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

for i in range(N):
    a.append(input().split())

check=0
ans=-1
for i in range(1,pow(2,N)):
    b=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    check=0
    for j in range(N):
        if 0x01 & (i >> j):
            for n in range(M+1):
                b[n] = b[n] + int(a[j][n])
    for k in range(1,M+1):
        if b[k] < X:
            check=1
    if check==0:
        if ans == -1 or ans > b[0]:
            ans = b[0]
print(ans)

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

def main():
    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(1<<n):
        S=[0]*m
        tmp=0
        for j in range(n):
            if (i>>j)&1==0:
                continue
            tmp+=C[j]
            B=A[j]
            for k,b in enumerate(B):
                S[k]+=b
        if min(S)>=x:
            ans=min(ans,tmp)
    print(-1 if ans==float('inf') else ans)
    
if __name__=='__main__':
    main()

Solution (Python):
n,m,x = map(int,input().split())
c,a = [],[]
for _ in range(n):
    l = list(map(int,input().split()))
    c.append(l[0])
    a.append(l[1:])
ans = float("inf")
for i in range(2**n):
    e = [0 for _ in range(m)]
    okane = 0
    for j in range(n):
        if (i >> j) & 1:
            katta = a[j]
            okane += c[j]
            for k in range(m):
                e[k] += katta[k]
    f = min(e)
    if f >= x:
        ans = min(ans,okane)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Solution (Python):
N, M, X = map(int,input().split())
A=[]
for i in range(N):
    A.append(list(map(int, input().split())))
    
pr=10**9
for s in range(2**N):
    x_m = [0]*13
    for i in range(N):
        b = (s >> i) & 1
        if b == 1:
            for j in range(M+1):
                x_m[j] += A[i][j]
 
    xOk = True
    for j in range(1,M+1):
        if x_m[j] < X:
            xOk = False
    
    if xOk == True:
        pr = min(pr, x_m[0])
 
if pr<10**9:
    print(pr)
else:
    print(-1)

Solution (Python):
import numpy as np
N,M,X=map(int,input().split())
C=np.zeros(N,dtype=int)
A=np.zeros([N,M],dtype=int)
for i in range(N):
    T=list(map(int,input().split()))
    C[i]=T[0]
    for j in range(M):
        A[i,j]=T[j+1]
a=np.zeros(N,dtype=int)
ans=-1
while a.all()!=1:
  if ((a@A)>=X).all():
    if ans==-1:
        ans=a@(C.T)
    elif a@(C.T)<ans:
        ans=a@(C.T)
  for i in range(N):
    if a[N-i-1]==0:
      a[N-i-1]=1
      break
    else:
      a[N-i-1]=0

if ((a@A)>=X).all():
  if ans==-1:
      ans=a@(C.T)
  elif a@(C.T)<ans:
      ans=a@(C.T)

print(ans)

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

res = 10 ** 9
for i in range(2 ** N):
    c = 0
    s = [0 for _ in range(M)]
    for j in range(N):
        if i >> j & 1:
            c += C[j]
            for k in range(M):
                s[k] += L[j][k]
    f = 1
    for j in range(M):
        if s[j] < X:
            f = 0
            break
    if f:
        res = min(res, c)

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

Solution (Python):
import sys
n,m,x= map(int, sys.stdin.readline().rstrip("\n").split())
lines = [ [int(s) for s in line.split()] for line in sys.stdin ]

books = {}
num = 0
for a in range(2):
    for b in range(2):
        for c in range(2):
            for d in range(2):
                for e in range(2):
                    for f in range(2):
                        for g in range(2):
                            for h in range(2):
                                for i in range(2):
                                    for j in range(2):
                                        for k in range(2):
                                            for l in range(2):
                                                books[num] = [a,b,c,d,e,f,g,h,i,j,k,l]
                                                num += 1
price = -1
skill = {}
for i in range(2**12-1):
    price_ = 0
    for j in range (m):
        skill[j] = 0
    for j in range(n):
        if books[i+1][j] == 1:
            price_  += lines[j][0]
            for k in range(m):
                skill[k] = skill[k] + lines[j][k+1]
        for k in range(m):
            if skill[k] < x:
                break
        else:
            if price == -1:
                price = price_
            else:
                price = min(price, price_)
print(price)

Solution (Python):
import numpy as np
from itertools import combinations
N, M, X = map(int, input().split())

row_list = []
C_list = []
for _ in range(N):
  row = list(map(int, input().split()))
  row = np.array(row)
  C_list.append(row[0])
  row_list.append(row[1:])

  
def check(subset, C_list, row_list, X):
  if len(subset) == 0:
    return 0, False
  
  cost_list = [C_list[ind] for ind in subset]
  cost = sum(cost_list)
  
  skill_arr = np.zeros(M)
  for ind in subset:
    skill_arr += row_list[ind]
    
  judge = np.min(skill_arr) >= X
    
  return cost, judge

output = np.inf
for j in range(N+1):
  for subset in combinations(range(N), j):
    cost, judge = check(subset, C_list, row_list, X)
    
    if judge and cost < output:
      output = cost

if output == np.inf:
  output = -1
  
print(output)

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(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 i in range(m):
        if x > smart[i]:
            ok = False
    
    if ok:
        ans = min(ans, cost_sum)

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

Solution (Python):
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): 
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): 
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} 
def bitArr(n):
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1


def money(arr):
	ans = 0
	for i in range(len(arr)):
		if arr[i]==1:
			ans+=c[i][0]
	return ans

n,m,x = readInts()
c = []
for i in range(n):
	c.append(readInts())

ans = 1000000000000

for arr in bitArr(n):
	tmp = [0]*m
	for i in range(n):
		if arr[i]==1:
			arrsSum(tmp,c[i][1:])
	if min(tmp)>=x:

		kari = money(arr)
		if kari<ans:
			ans = kari

if ans==1000000000000:
	ans = -1

print(ans)

Solution (Python):
def resolve():

    n, m,x = map(int, input().split())
    c=[]
    a=[]
    ans=10**13
    nedan=0
    rikai=[0]*m
    for i in range(n):
        A = list(map(int, input().split()))
        c.append(A[0])
        a.append(A[1:])
        for j in range(m):
            rikai[j]+=a[i][j]

    if min(rikai)>=x:
        for Bin in range(1,2**n):
            rikai = [0] * m
            nedan = 0
            for hon in range(n):
                if (Bin>>hon) & 1:
                    for aru in range(m):
                        rikai[aru]+=a[hon][aru]
                    nedan+=c[hon]
            if min(rikai)>=x:
                ans=min(ans,nedan)
        print(ans)

    else:
        print(-1)
resolve()

Solution (Python):
N, M, X = map(int, input().split())
C, A = [], []
for _ in range(N):
    tmp = [int(a) for a in input().split()]
    C.append(tmp[0])
    A.append(tmp[1:])

mi = 1 << 100
for binary in range(1 << N):
    B = [0] * M
    c = 0
    for i in range(N):
        if binary >> i & 1:
            c += C[i]
            for j in range(M):
                B[j] += A[i][j]
    if min(B) >= X:
        mi = min(c, mi)
print(mi if mi < 1 << 99 else -1)

Solution (Python):
import itertools
import numpy as np

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




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

l = [True, False]
    


value_list = []
for is_buy_list in itertools.product(l, repeat=n):
    sum_l = np.array([0] * (m + 1))
    for i in range(n):
        
        if is_buy_list[i]:
            sum_l += np.array(ca_list[i])
            

    
    if min(sum_l[1:]) >= x:
        
        value_list.append(sum_l[0])


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

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

anslis = [1000000000000] * (2**N)

for i in range(2**N):
    kin = 0
    skil = [0] * M
    for j in range(N):
        if((i >> j) & 1):
            kin = kin + list[j][0]
            for k in range(M):
                skil[k] = skil[k] + list[j][k+1]

    if min(skil) >= X:
        anslis[i] = kin

if min(anslis) == 1000000000000:
    print(-1)
else:
    print(min(anslis))

Solution (Python):
def DFS(v):
    global rst
    if v<=N:
        L.append(v)
        DFS(v+1)
        L.pop()
        DFS(v+1)
    else:
        cost=[0]*M
        for i in L:
            for j in range(M):
                cost[j]+=CA[i-1][j+1]

        for i in range(M):
            if cost[i]<X:
                break
        else:
            out=0
            for j in L:
                out+=CA[j-1][0]
            rst=min(rst,out)

N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for _ in range(N)]
rst=10**9
L=[]

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

Solution (Python):
DEBUG = False

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

if DEBUG:
    print(A)
    print(C)

max_money = 10**5 * N + 1
ans_money = max_money

for i in range(2**N):
    bit = bin(i)[2::]
    bit = bit.zfill(N)
    if DEBUG:
        print("i: {}, bit: {}".format(i, bit))
    tmp_money = 0
    tmp_algorythm = [0] * M
    for j, b in enumerate(bit):
        if b == '1':
            tmp_money += C[j]
            for k, c in enumerate(A[j]):
                tmp_algorythm[k] += c
    if DEBUG:
        print("tmp_money: {}, tmp_algorythm: {}".format(tmp_money, tmp_algorythm))
    if len(list(filter(lambda x: x < X, tmp_algorythm))) == 0:
        ans_money = min(tmp_money, ans_money)
        if DEBUG:
            print("ans_money: {}".format(ans_money))
        

if ans_money == max_money:
    print(-1)
else:
    print(ans_money)

Solution (Python):
import numpy as np

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

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

cost = float("inf")

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

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

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


ans = 10**10
for b in range(2**n):
  skils = [0]*m
  tmp = 0
  
  for i in range(n):
    if b&(1<<i):
      for j in range(m):
        skils[j] += li[i][j+1]
      tmp += li[i][0]

        
  if min(skils)>=x:
    ans = min(ans, tmp)

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

Solution (Python):
import itertools
n,m,x = map(int,input().split(" "))
books = []
for i in range(n):
    books.append(list(map(int,input().split(" "))))
min_cost = 12*10**5+1
book_list = list(itertools.product(range(2),repeat = n))
for book in book_list:
    skills = [x for i in range(m)]
    cost = 0
    for j in range(len(book)):
        if book[j] == 1:
            cost += books[j][0]
            for k in range(m):
                skills[k] -= books[j][k+1]
    flag = True
    for j in range(m):
        if skills[j] > 0:
            flag = False
    if flag and cost != 0:
        min_cost = min(min_cost,cost)
if min_cost == 12*10**5+1:
    print(-1)
else:
    print(min_cost)

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

l = list()
ans = []

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


for i in range(1, 2**n):
    num = format(i, '0' + str(n) + 'b')
    l.append(num)



list_len = len(l)

s = 0

tmp = [0]*(m+1)

for i in range(0, list_len):
    w_len = m
    num = l[i]
    for j in range(0, n):
        if int(num[j]) == 1:
            for z in range(0, m+1):
                tmp[z] += a_list[j][z]
    
    if len(list(filter(lambda number: number >= x, tmp[1:]))) == m:
        ans.append(tmp[0])
    tmp = [0]*(m+1)



if ans == []:
    print(-1)
else:
    print(min(ans))

Solution (Python):
import sys
import math
import itertools
import collections

def solve(N,M,X,C,A):
    ans = []
    for bit in range(2**N):
        total = 0
        dic = {key:0 for key in range(M)}
        for i in range(N):
            if(bit & (1 << i)):
                total += C[i]
                for n,a in enumerate(A[i]):
                    dic[n]+=a
        for m in range(M):
            if(dic[m] < X):
                break
        else:
            ans.append(total)
    return min(ans) if(ans != []) else -1
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
def main():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int,input().split()))
        C.append(tmp.pop(0))
        A.append(tmp)
    
    print(solve(N,M,X,C,A))

if __name__ == "__main__":
    main()

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

min_ = 10**10

for i in range(2**N):
    understanding = [0 for j in range(M)]
    cost = 0
    for j in range(N):
        if (i>>j)&1:
            for k in range(M):
                understanding[k] += books[j][k+1]
            cost += books[j][0]
    if all([a >= X for a in understanding]):
        min_ = min(min_,cost)

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

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, X = map(int, input().split())
    C = []
    A = []
    for _ in range(N):
        B = list(map(int, input().split()))
        C.append(B[0])
        A.append(B[1:])
    answer = float("inf")
    for i in range(2 ** N):
        ans = [0] * M
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                for m in range(M):
                    ans[m] += A[j][m]
                cnt += C[j]
        c = 0
        for m in range(M):
            if ans[m] >= X:
                c += 1
        if c == M:
            if cnt < answer:
                answer = cnt
    if answer == float("inf"):
        print(-1)
    else:
        print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations

def main():
    N, M, X = [int(i) for i in input().split()]
    C, A = [], []
    for _ in range(N):
        ca = [int(i) for i in input().split()]
        C.append(ca[0])
        A.append(ca[1:])

    for m in range(M):
        if sum(a[m] for a in A) < X:
            print(-1)
            return

    sets = []
    comb_ix = [comb for i in range(1, len(A) + 1) for comb in combinations(range(len(A)), i)]
    for m in range(M):
        tmp_lst = []

        for comb in comb_ix:
            a = [a[m] for i, a in enumerate(A) if i in comb]
            if sum(a) >= X:
                tmp_lst.append(comb)
        
        sets.append(frozenset(tmp_lst))

    intersection = set.intersection(*map(set, sets))
    res = sum(C)
    for comb in intersection:
        sum_c = sum(c for i, c in enumerate(C) if i in comb)
        if sum_c < res:
            res = sum_c

    print(res)

main()

Solution (Python):
def resolve():
    n, m, x = map(int, input().split())
    A, C = [], []
    for _ in range(n):
        c_a = list(map(int, input().split()))
        c = c_a.pop(0)
        A.append(c_a)
        C.append(c)

    def dfs(N, B, D):
        if N == n:
            if min(B) < x:
                return -1
            else:
                return D
        r = dfs(N + 1, [x + y for (x, y) in zip(B, A[N])], D + C[N])
        l = dfs(N + 1, B, D)
        if l == r == -1:
            return -1
        else:
            if l == -1:
                return r
            elif r == -1:
                return l
            else:
                return min([l, r])

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

Solution (Python):
def resolve():
    import itertools

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

    prices = []
    gains = []
    for i in range(n):
        price, *gain = list(map(int, input().split()))
        prices.append(price)
        gains.append(gain)

    combs = []
    for i in range(n + 1):
        for comb in itertools.combinations(list(range(n)), i):
            combs.append(comb)

    successful = []
    for comb in combs:
        levels = [0] * m
        sum = 0

        for i in comb:
            sum += prices[i]
            for j in range(m):
                levels[j] += gains[i][j]

        levels = list(filter(lambda item: item >= x, levels))
        if len(levels) == m:
            successful.append(sum)

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

Solution (Python):
import numpy as np

N,M,X = map(int, input().split(' '))
C=[]
maxNum=999999999
dmaxNum=999999999
for i in range(N):
  C.append(list(map(int, input().split(' '))))
for i in range(2**N):
  ar=[0]*(M+1)
  for j in range(N):
    if (i & 2**j) != 0:
      ar = [x + y for (x, y) in zip(ar, C[j])]
  if (np.array(ar[1:])>=X).all()>0:
    maxNum=min(maxNum,ar[0])
if maxNum==dmaxNum:
  print(-1)
else:
  print(maxNum)

Solution (Python):
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

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

def read_s_list_loop(n):
    return [input() for _ in range(n)]

def bit_cal(n):
    return_list = ['']* (2 ** n)
    for i in range(2 ** n):
        for j in range(n):
            if ((i >> j) & 1):
                return_list[i] = return_list[i] + '1'
            else:
                return_list[i] = return_list[i] + '0'
    return return_list

N,M,X = read_int_map()
Cn = [list(read_int_map()) for _ in range(N) ]

ans = float('inf')
bit_list = bit_cal(N)
for bit in bit_list:
    m_list = [0]*M
    price = 0
    for i in range(N):
        if bit[i] == '1':
            price += Cn[i][0]
            for j in range(1,M+1):
                m_list[j-1] += Cn[i][j]
    flag = True
    for m in m_list:
        if m < X:
            flag = False
            break
    if flag:
        ans = min(price,ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

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

A = [[] for i 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 sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, m, x = MAP()
arr = [LIST() for _ in range(n)]
c = [arr[i][0] for i in range(n)]
a = [arr[i][1:] for i in range(n)]

ans = inf
for i in range(2 ** n):
    tmp = [0 for _ in range(m)]
    cst = 0
    for j in range(n):
        if i - (i >> (j + 1)) * (2 ** (j + 1)) >= 2 ** j:
            for k in range(m):
                tmp[k] += a[j][k]
            cst += c[j]
    flag = True
    for j in range(m):
        if tmp[j] < x:
            flag = False
    if flag:
        ans = min(ans, cst)
if ans == inf:
    print(-1)
else:
    print(ans)

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

INF = float("inf")
ans = INF

for i in range(2**n):
    A = [0] * m
    price = 0

    
    for j in range(n):
        if i>>j & 1:
            price += ca[j][0]
            for k in range(m):
                A[k] += ca[j][k+1]

    gtX = True
    for j in range(m):
        if A[j] < x:
            gtX = False
            break
    if gtX:
        ans = min(ans, price)

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

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

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

for bit in range(2**17):
    sum = 0
    skill = [0] * M
    for i in range(N):
        if random.randint(0, 1):
            sum += C[i]
            for j in range(M):
                skill[j] += A[i][j]
    ok = True
    for j in range(M):
        if skill[j] < X:
            ok = False
    if ok:
        ans = min(ans, sum)
if ans == INF:
    ans = -1
print(ans)

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

ans = 1<<60

for i in range(1<<n):
    score = [0]*m
    money = 0
    for j in range(n):
        if (1<<j) & i != 0:
            money += c[j]
            for k in range(m):
                score[k] += a[j][k]
    if min(score) >= x:
        ans = min(ans,money)

if ans == 1<<60:
    print(-1)
else:
    print(ans)

Solution (Python):
import numpy as np
from itertools import product
INF = 10**9

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

choose = [True, False]

min_price = INF

for s in product([True, False], repeat=N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if s[i]:
            knowledge += A[i]
            price += C[i]
    if np.any(knowledge < X):
        continue
    if min_price == -1:
        min_price = price
    min_price = min(min_price, price)

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

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M, X  = [int(x) for x in stdin.readline().rstrip().split()]

CA = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

dp = [[[0 for _ in range(M)] for _ in range(4)] for _ in range(N+1)]
dp_money = [[0 for _ in range(2)] for _ in range(N+1)]

tm = [0 for _ in range(2**N)] 
tl = [[0 for _ in range(M)] for _ in range(2**N)]

knowledge_list = [[0 for _ in range(M)]]
money_list = [0]

for i in range(N):
    C = CA[i][0]
    A = CA[i][1:]

    
    tmp2 = []
    
    for i, knowledge in enumerate(knowledge_list):
        tmp = []
        for k in range(len(knowledge)):
            tmp.append(knowledge[k] + A[k])
        
        tmp2.append(tmp)
        money_list.append(money_list[i]+C)

    knowledge_list = knowledge_list + tmp2

ans = INF
for i in range(len(money_list)):
    if min(knowledge_list[i]) >= X:
        ans = min(ans, money_list[i])

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