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):
from sys import maxsize
import numpy as np


def check(ls, x):
    for i in range(1, len(ls)):
        if ls[i] < x:
            return False
    return True


def convert(b, n):
    diff = n - len(b)
    return ('0' * diff + b)[::-1]


n, m, x = map(int, input().split())
ls = []
a = [i for i in range(n)]
for i in range(n):
    ls.append(list(map(int, input().split())))
dp = [0] * ((1 << n) + 1)
for i in range(n):
    dp[1 << i] = np.array(ls[i])
total_cost = maxsize
for subset in range(1, (1 << n)):
    b = bin(subset)[2:]
    b = convert(b, n)
    a = np.zeros(m + 1)
    for i in range(n):
        if int(b[i]):
            a += dp[1 << i]
    dp[subset] = a
    if check(dp[subset], x):
        total_cost = min(total_cost, dp[subset][0])
if total_cost ==maxsize:
    print(-1)
else:  
    print(int(total_cost))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)


def dfs(i, res, under):
    if i == n:
        if min(under) < x:
            return -1
        else:
            return res
    l = dfs(i + 1, res + c[i], [s + t for (s, t) in zip(under, a[i])])
    r = dfs(i + 1, res, under)
    if l == r == -1:
        return -1
    else:
        if l == -1:
            return r
        elif r == -1:
            return l
        else:
            return min(l, r)


n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
c = [a[s][0] for s in range(n)]
a = [a[t][1:] for t in range(n)]
und = [0]*m
ans = []
print(dfs(0, 0, und))

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

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

OK = True
CA = np.array(CA)
sums = np.sum(CA,axis=0)
for i in range(1,M+1):
  if sums[i] < X:
    OK = False
    break

if OK == False:
  print(-1)
else:
  As = []
  for A in combinations_with_replacement(range(0, N),N):
    As.append(tuple(set(A)))
  As = list(map(list, set(As)))
  min_ = sums[0]
  for i in As:
    mini_CA = []
    for j in i:
      mini_CA.append(CA[j-1])
    mini_CA = np.array(mini_CA)
    OK2 = True
    sums = np.sum(mini_CA,axis=0)
    for k in range(1,M+1):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
  print(min_)

Solution (Python):
n, m, x = map(int, input().split())
a = [[] for i in range(n)]
c = [0] * n
for i in range(n):
	c[i], *a[i] = map(int, input().split())
ans = 1e9
for mask in range(2 ** n):
	cost = 0
	b = [0] * m
	for i in range(n):
		if mask & (1 << i):
			cost += c[i]
			for j in range(m):
				b[j] += a[i][j]
	cnt = True
	for j in range(m):
		cnt &= b[j] >= x
	if cnt:
		ans = min(ans, cost)
			
if ans < 1e9:
	print(ans) 
else:
	print(-1)

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

N, M, X = list(map(int, input().split()))
conditions = product([0, 1], repeat=N)
A = np.array([list(map(int, input().split())) for i in range(N)])
succeed = []
for c in conditions:
    p = A * np.array(c).reshape((N, 1))
    res = p.sum(axis=0)
    if np.all(res[1:] >= X):
        succeed.append(res[0])
print(min(succeed) if len(succeed) > 0 else -1)

Solution (Python):







import numpy as np


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

CAarray = np.array(CA)
C = CAarray[:,0]
A = CAarray[:,1:M+2]

if np.count_nonzero(np.sum(A, axis=0) < X) != 0:
    print(-1)
    exit()

Answer = np.sum(C)

for i in range(0,2**N):
    ll = [int(x) for x in list(str(format(i,'b').zfill(N)))]
    l = np.array(ll)

    if np.count_nonzero(np.dot(A.T,l.T) >= X) == M:
        if Answer >= np.dot(C.T,l.T):
            Answer = np.dot(C.T,l.T)

print(Answer)

Solution (Python):

import sys
import itertools



def main():
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    anss = []
    for i in range(2 ** N):
        s = 0
        arr = [0] * M
        for j in range(N):
            if i >> j & 1:
                s += CA[j][0]
                arr = python_list_add(arr, CA[j][1])
            if all([x >= X for x in arr]):
                anss.append(s)
    print(min(anss) if anss else -1)

    return


def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]


if __name__ == '__main__':
    main()

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

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

OK = True
CA = np.array(CA)
sums = np.sum(CA,axis=0)
for i in range(1,M+1):
  if sums[i] < X:
    OK = False
    break

if OK == False:
  print(-1)
else:
  
  
  
  
  min_ = sums[0]
  hoge = []
  kouho = list(range(1,N+1))
  for i in combinations_with_replacement(kouho, N):
    hoge.append(list(set(i)))
  hoge = list(map(list, set(map(tuple, hoge))))
  for i in hoge:
    mini_CA = []
    for j in i:
      mini_CA.append(CA[j-1])
    mini_CA = np.array(mini_CA)
    OK2 = True
    sums = np.sum(mini_CA,axis=0)
    for k in range(1,M+1):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
  print(min_)

Solution (Python):
if __name__=="__main__":
    N, M, X = map(int, input().split(' '))
    book_list = [None]*N
    min_price = -1
    for i in range(N):
        book_list[i] = list(map(int, input().split(' ')))

    for i in range(2 ** N):
        comp_list = []
        for j in range(N):
            if ((i >> j) & 1):
                if comp_list == []:
                    comp_list = book_list[j]
                else:
                    comp_list = [a + b for a, b in zip(comp_list, book_list[j])]

                if all(comp >= X for comp in comp_list[1:]):
                    if min_price == -1:
                        min_price = comp_list[0]
                    elif comp_list[0] <= min_price:
                        min_price = comp_list[0]
    print(min_price)

Solution (Python):
import numpy as np

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

buy = [{"c":0,"a":np.zeros(m)}]
for i in range(len(C)):
    temp = []
    for j in buy:
        temp.append(j)
        temp.append({"c":j["c"]+C[i],"a":j["a"]+np.array(A[i])})
    buy = temp


    
res = 10**7
for i in buy:
    if np.all(i["a"]>=x):
        res = min(i["c"],res)
if res == 10**7:
    res = -1
    
print(res)

Solution (Python):
from itertools import combinations
N, M, X = map(int, input().split())
books = []
for _ in range(N):
    books.append(list(map(int, input().split())))
P = []
for i in range(1, N+1):
    for item in list(combinations(books, i)):
        P.append(item)
ans = 10 ** 9 + 1
for items in P:
    price = 0
    chk = [0] * M
    for p in items:
        price += p[0]
        for i, item in enumerate(p[1:]):
            chk[i] += item
        if all(c >= X for c in chk):
            ans = min(ans, price)
            break
if ans == 10 ** 9 + 1:
    ans = -1
print(ans)

Solution (Python):
def roots(l,i,v,ans):
    if i<len(l):
        roots(l,i+1,v,ans)
        roots(l,i+1,v+[l[i]],ans)
        return
    else:
        if v!=[]:
            ans.append(v)
        return ans

def sumL(l):
    ans=[0]*len(l[0])
    for i in range(len(l)):
        for j in range(len(l[i])):
            ans[j]+=l[i][j]
    return ans

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

ans=[]
roots(l,0,[],ans)

minV=10**10

for i in ans:
    flag=True
    s=sumL(i)
    for j in s[1:]:
        if j<x:
            flag=False
            break
    if flag and minV>s[0]:
        minV=s[0]
if minV==10**10:
    print(-1)
else:
    print(minV)

Solution (Python):
import math

N, M, X = (int(x) for x in input().split())
comp = [0] * M
CA = []
for i in range(N):
    CA.append(list(map(int,input().split())))


minimum = 10 ** 5 * 14
for i in range(2**N):
    comp = [0] * (M + 1)
    for j in range(N):
        if (i >> j) & 1:
            comp = [x + y for (x, y) in zip(comp, CA[j])]
    flag = True
    for j in range(M + 1):
        if j == 0:
            continue
        if comp[j] < X:
            flag = False
            break
    if minimum > comp[0] and flag:
        minimum = comp[0]

if minimum == 10 ** 5 * 14:
    minimum = -1
print(minimum)

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

from operator import add

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

A=[]
C=[]
for n in range(N):
	C.append(CA[n][0])
	A.append(CA[n][1:])


ans = sum(C)+1
for i in range(1 << N):

	tmpA = [0]*M
	c = 0
	
	for j in range(N):
		if ((i >> j) & 1) == 0: continue

		tmpA = map(add, tmpA, A[j])
		c += C[j]
	
	if min(tmpA) < X: continue
	
	ans = min(ans, c)


print( ans if ans <= sum(C) else -1)

Solution (Python):
n,m,x = map(int,input().split())
a = [[]for i in range(n)]
ans = -1
for i in range(n):
    a[i] = list(map(int,input().split()))
for i in range(2**n):
    b = str(bin(i))
    c = [0]*(m+1)
    cscore = 0
    for j in range(0,len(b)-2):
        if b[-j-1] == "1":
            for k in range(m+1):
                c[k]+=a[j][k]
    cscore = c[0]
    for j in range(m):
        if c[j+1] < x:
            cscore = -1
    if cscore!=-1:
        if ans == -1:
            ans = cscore
        else:
            ans = min(ans,cscore)

print(ans)

Solution (Python):
import sys

lines = sys.stdin.readlines()
N, M, X = map(int, lines[0].split())
A = []
C = []

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


def full_search():
    costs = []
    for i in range(2**N):
        vals = [0] * M
        cost = 0

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

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

        combination_ok = True
        for m in range(M):
            if vals[m] >= X:
                continue
            else:
                combination_ok = False
                break

        if combination_ok:
            costs.append(cost)
    return costs

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

Solution (Python):
N, M, X = map(int, input().split())
C = []; A = []; T = []
for _ in range(N):
    s = list(map(int, input().split()))
    C.append(s[0])
    A.append(s[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) & 1:
            cost_sum += C[i]
            for j in range(M):
                smart[j] += A[i][j]
    ok = True
    if min(smart) < X:
        ok = False
    if ok:
        ans = min(ans, cost_sum)

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

Solution (Python):
import math
N , M , X =  map(int,input().split())
A = {}
B = {}
ANS = 100000000000
for i in range(1,N+1):
    A[i]=list(map(int,input().split()))
for i in range(1,2**N):
    l = str(bin(i))
    n = len(l)
    ans=0
    for s in range(1,M+1):
        B[s]=0
    for k in range(1,n+1):
        if l[-k] == "1":
            ans = ans + A[k][0]
            for s in range(1,M+1):
                B[s] += A[k][s]
    if all((B[l] >= X for l in range(1,M+1))):
        ANS = min(ans,ANS)
if ANS == 100000000000:
    print("-1")
else:
    print(ANS)

Solution (Python):
import itertools
import numpy as np


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


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

cost = []

skill = list(zip(*CA))

for i in range(1, M+1):
    if sum(skill[i]) < X:
        print(-1)
        exit()

for i in range(1, N+1):
    for balls in list(itertools.combinations(CA, i)):
        test = np.zeros(M+1)
        for j in balls:
            jtest = np.asarray(j)
            test = test + jtest

        if min(test[1:])>=X:
            cost.append(test[0])

print(int(min(cost)))

Solution (Python):
import numpy as np

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

ans = 10**20
for i in range(2 ** N):
    cost = 0
    sk = np.zeros(M, dtype=int)
    for j in range(N):  
        if ((i >> j) & 1):  
            cost += C[j]
            sk += A[j, :]
    if all(s >= X for s in sk):
        ans = min(ans, cost)

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

Solution (Python):


import itertools
import sys

N, M, X  = map(int, input().split())
money = []
A = []
ans = []
for _ in range(N):
    nums = [int(x.strip()) for x in input().split(' ') ]
    money.append(nums[0])
    nums.pop(0)
    A.append(nums)
num_money = []
for index, num in enumerate(money):
    num_money.append(index)
    
def run(lis, num, A, X, M, ans, money):
    ans_list = []
    for team in itertools.combinations(lis, num):
        count = 0
        for i in range(M):
            tmp = 0
            for j in list(team):
                tmp += A[j][i]
            if tmp >= X:
                count += 1
        if count == M:
            tmp_ans = []
            for n in list(team):
                tmp_ans.append(money[n])
            ans_list.append(sum(tmp_ans))
    if not len(ans_list) == 0:
        ans.append(min(ans_list))
    
    return ans
        
for i in range(1, N+1):
    ans = run(num_money, i, A, X, M, ans, money)
    
if not len(ans) == 0:
    print(min(ans))
    
else:
    print(-1)

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

ans=10**9
for i in range(2**n):
  t_ans=0
  us=[0 for j in range(m)]
  for k in range(n):
    if (i>>k)&1:
      book=l[k]
      t_ans+=book[0]
      for p in range(m):
        us[p]+=book[p+1]

  if min(us)>=x:
    ans=min(ans,t_ans)

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

Solution (Python):
N, M, X = map(int, input().split())
C = []; A = []; T = []
for _ in range(N):
    s = list(map(int, input().split()))
    C.append(s[0])
    A.append(s[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
    if min(smart) < X:
        ok = False
    if ok:
        ans = min(ans, cost_sum)

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

Solution (Python):


import itertools
import sys

N, M, X  = map(int, input().split())
money = []
A = []
ans = []
for _ in range(N):
    nums = [int(x.strip()) for x in input().split(' ') ]
    money.append(nums[0])
    nums.pop(0)
    A.append(nums)
num_money = []
for index, num in enumerate(money):
    num_money.append(index)
    
def run(lis, num, A, X, M, ans, money):
    ans_list = []
    for team in itertools.combinations(lis, num):
        count = 0
        for i in range(M):
            tmp = 0
            for j in list(team):
                tmp += A[j][i]
            if tmp >= X:
                count += 1
        if count == M:
            tmp_ans = []
            for n in list(team):
                tmp_ans.append(money[n])
            ans_list.append(sum(tmp_ans))
    if not len(ans_list) == 0:
        ans.append(min(ans_list))
    
    return ans
        
for i in range(1, N+1):
    ans = run(num_money, i, A, X, M, ans, money)
    
if not len(ans) == 0:
    print(min(ans))
    
else:
    print(-1)

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

ans=10**9
for i in range(2**n):
  t_ans=0
  us=[0 for j in range(m)]
  for k in range(n):
    if (i>>k)&1:
      book=l[k]
      t_ans+=book[0]
      for p in range(m):
        us[p]+=book[p+1]

  if all([q>=x for q in us]):
    ans=min(ans,t_ans)

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

Solution (Python):


import itertools
import sys

N, M, X  = map(int, input().split())
money = []
A = []
ans = []
for _ in range(N):
    nums = [int(x.strip()) for x in input().split(' ') ]
    money.append(nums[0])
    nums.pop(0)
    A.append(nums)
num_money = []
for index, num in enumerate(money):
    num_money.append(index)
    
def run(lis, num, A, X, M, ans, money):
    ans_list = []
    for team in itertools.combinations(lis, num):
        count = 0
        for i in range(M):
            tmp = 0
            for j in list(team):
                tmp += A[j][i]
            if tmp >= X:
                count += 1
        if count == M:
            tmp_ans = []
            for n in list(team):
                tmp_ans.append(money[n])
            ans_list.append(sum(tmp_ans))
    if not len(ans_list) == 0:
        ans.append(min(ans_list))
    
    return ans
        
for i in range(1, N+1):
    ans = run(num_money, i, A, X, M, ans, money)
    
if not len(ans) == 0:
    print(min(ans))
    
else:
    print(-1)

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

c = [0 for _ in range(n)]
A = [0 for _ in range(n)]
for i in range(n):
	line = [int(j) for j in input().split()]
	c[i] = line[0]
	A[i] = line[1:]

ans = 100111000010

for s in range(1<<n):
	alg = [0 for _ in range(m)]
	cost = 0
	judge = True
	for i in range(n):
		if s>>i&1:
			cost += c[i]
			for j in range(m):
				alg[j] += A[i][j]

	for j in range(m):
		if alg[j] < x:
			judge = False
	
	if judge:
		ans = min(cost, ans)

if not judge:
	print(-1)
else:
	print(ans)

Solution (Python):
n,m,x = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
ans = float('inf')

for i in range(2**n):
    sum = [0]*(m+1)
    
    for j in range(n):
        
        if (i >> j) & 1:
            for k in range(m+1):
                sum[k] += l[j][k]
    if sum[0] < ans:
        for a in range(1,m+1):
            if sum[a] < x:
                break
        else:
            ans = sum[0]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
import itertools
n, m, x = map(int, input().split())
C = [0] * n
A = [[0] * m for i in range(n)]

mlist = [0] * m
for i in range(n):
    books = list(map(int, input().split()))
    C[i] = books[0]
    for j in range(m):
        A[i][j] = books[j + 1]

mincost = sys.maxsize
for i in range(2**n):
    sumlist = [0] * m
    currentcost = 0
    for j in range(n):
        if ((i >> j) % 2) == 1:
            for k in range(m):
                sumlist[k] += A[j][k]
            currentcost += C[j]
    if min(sumlist) >= x:
        if currentcost < mincost:
            mincost = currentcost

if mincost == sys.maxsize:
    print("-1")
else:
    print(mincost)

Solution (Python):

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

import copy
result = []
def test(i,i_sum,cost):
    
    flag = 0
    if i <= n:
        for j in range(m):
            if i_sum[j] < x:
                flag = 1
                break

        if flag == 1:
                test(copy.deepcopy(i)+1, i_sum[:],cost[:])

                for j in range(1,m+1):
                    i_sum[j-1] += sp[i-1][j]
                cost[0] += sp[i-1][0]
                test(copy.deepcopy(i)+1, i_sum[:],cost[:])
        else:
            result.append(cost[0])
test(0,[0]*m,[0])

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

Solution (Python):
from itertools import compress

import numpy as np

N, M, X = [int(x) for x in input().split()]
CA = np.array([[int(x) for x in input().split()] for _ in range(N)])

minimal_cost = None
for bought_book in range(1, 2**N):
    bought_book = [int(b) for b in ("{:0" + str(N) + "b}").format(bought_book)]

    CA_filtered = np.array(list(compress(CA, bought_book)))

    total_cost = sum(CA_filtered[:, 0])
    total_understanding = np.sum(CA_filtered[:, 1:], axis=0) >= X
    if np.all(total_understanding):
        minimal_cost = min(minimal_cost or total_cost, total_cost)

print(minimal_cost if minimal_cost is not None else "-1")

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,X = map(int, readline().split())
data = np.array(read().split(), np.int64)

data = data.reshape(N,-1)
C = data[:,0]
A = data[:,1:]

cost = np.zeros(1<<N, np.int64)
ability = np.zeros((1<<N, M), np.int64)
for i in range(N):
    cost[1<<i:1<<(i+1)] = cost[:1<<i] + C[i]
    ability[1<<i:1<<(i+1)] = ability[:1<<i] + A[i]

ok = np.all(ability >= X, axis=1)

x = cost[ok]
answer = -1 if len(x) == 0 else x.min()
print(answer)

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


ans = 9999999999

for el in itertools.product([0,1],repeat=n):
  
  cav = [0]*(m+1)
  for i in range(n):
    if el[i] == 1:
      for j in range(m+1):
        cav[j] += c[i][j]

  if x > min(cav[1:m+1]):
    pass
  else:
    ans = min(cav[0],ans)

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

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

a = [[int(i) for i in input().split()] for _ in range(n)] 



sum1 = [0] * (m+1)
sum2 = [0] * (m+1)

ans = 0

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


for i in range(n):
    for j in range(m+1):
        sum1[j] += a[i][j]
for  i in range(1,m+1):
    if sum1[i] < x:
        sum1[0] = -1
        print(-1)
        exit()

ans = sum1[0]

for i in range(2**n):
    for j in range(n):
        for k in range(m+1):
            
            sum2[k] +=  a[j][k]*st[i][j]
    
    for i in range(1,m+1):
        if sum2[i]  < x:
            sum2[0]= 100000000
    ans = min(sum2[0],ans)
    
    sum2 = [0] * (m+1)

print(ans)

Solution (Python):
N,M,X=map(int,input().split())
l=[]
for i in range (N):
  l.append(list(map(int,input().split())))
ans=10000000
for i in range(2**N):
  score=[0]*M
  coin=0
  for j in range(N):
    if i>=2**(N-1-j):
      for p in range(M):
        score[p]+=l[j][p+1]
      coin+=l[j][0]
      i-=2**(N-1-j)
  flag=0
  for q in range(M):
    if score[q]<X:
      flag=1
  if flag==0:
    if ans>coin:
      ans=coin
if ans==10000000:
  print("-1")
else:
  print(ans)

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

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

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

ans = float("INF")
p = [i for i in range(1, N+1)]

for k in range(1, N+1):
  for v in combinations(p, k):
    smart = [0] * M
    cost_sum = 0
    for i in v:
      cost_sum += C[i-1]
      for j in range(M):
        smart[j] += A[i-1][j]
    ok = True
    for j in range(M):
      if smart[j] < X:
        ok = False
    if ok:
      ans = min(ans, cost_sum)

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

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


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


def dfs(asum, b):
    global N, M, X
    rst = 10 ** 8
    if b == N:
        if all(asum[i] >= X for i in range(1, M + 1)):  
            rst = asum[0]
    else:
        
        rst = min(rst, dfs(asum, b + 1))
        
        
        asum2 = tuple(asum[i] + C[b][i] for i in range(M + 1))  
        rst = min(rst, dfs(asum2, b + 1))

    return rst


rst = dfs(tuple([0] * (M + 1)), 0)
ans = rst if rst < 10 ** 8 else -1
print(ans)

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

N,M,X = map(int,readline().split())
data = [None] * N
for i in range(N):
  d = list(map(int,input().split()))
  c = d[0]
  target = d[1:]
  data[i] = [c,target]

ans = 10 ** 9
for i in range(2 ** N):
  cost = 0
  skills = [0] * M
  for j in range(N):
    if (i >> j) & 1:
      cost += data[j][0]
      for k in range(len(data[j][1])):
        skills[k] += data[j][1][k]
  if ans > cost:
    for k in range(len(skills)):
      if skills[k] < X:
        break
    else:
      ans = cost
      
if ans == 10 ** 9:
  print(-1)
else:
  print(ans)

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

C=[]
A=[]
for n in range(N):
  AC=list(map(int,input().split()))
  C.append(AC[0])
  A.append(AC[1:])
ans=10**9

for n in range(2**N):
  total=0
  und=[0]*M
  for j in range(N):
    if n >> j & 1:
      total+=C[j]
      for m in range(M):
        und[m]+=A[j][m]
  if X <= min(und):
    ans=min(total,ans)
if ans==10**9:
  print(-1)
else:
  print(ans)

Solution (Python):
n,m,x=map(int,input().split())
c=[0]*n
a=[0]*n
ans=10**10
for i in range(n):
  d,*b=map(int,input().split())
  c[i]=d
  a[i]=b
import numpy as np
a=np.array(a)
from itertools import product
r=list(product([0,1],repeat=n))
for i in r:
  tmp=np.array([0]*m)
  cost=0
  for j,k in enumerate(i):
    tmp+=k*a[j]
    cost+=k*c[j]
  if all(tmp>=x):
    ans=min(ans,cost)
if ans>10**9:
  ans=-1
print(ans)

Solution (Python):
import itertools
import numpy as np
N,M, X= list(map(int,input().split()))
l = list(itertools.product([0,1], repeat=N))

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

r = float('inf')
for i in l:
  cost = 0
  i = np.array(i).reshape( N,-1)
  f = i*C
  sum_f = f.sum(axis = 0)
  
  if all(sum_f[1:]>=X):
    if r >sum_f[0] :
      r = sum_f[0]
    
if r == float('inf') :
  print(-1)
else :
  print(r)

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

ans = 10 ** 18
for bit_state in range(1 << n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if bit_state & (1 << i):
            for j in range(m):
                tmp[j] += info[i][j + 1]
            cost += info[i][0]

    for j in range(m):
        if tmp[j] < x:
            break
    else:
        ans = min(cost, ans)

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

Solution (Python):
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,X = LI()
CA = np.array([LI() for _ in range(N)])
ans = float('INF')
for i in range(2**N):
    bit = np.array([[i>>j&1 for j in range(N)]]).T
    t = np.sum(CA*bit,axis=0)
    if np.all(t[1:]>=X):
        ans = min(ans,t[0])
print(ans if ans !=float('INF') else -1)

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

ans = 10**18

for b in range(2**N):
  b = bin(b)[2:].zfill(N)
  pay = [0]*(M+1)
  count = 0
  for i in range(N):
    if b[i] == "1":
      pay = [x + y for (x, y) in zip(pay, l[i])]
  for j in range(1,M+1):
    if pay[j] >= X:
      count += 1
  if count == M:
    ans = min(ans,pay[0])
if ans != 10**18:
  print(ans)
else:
  print(-1)

Solution (Python):
from itertools import product
n, m, x = map(int, input().split())
ca = [tuple(map(int, input().split())) for _ in range(n)]
INF = 10**18
ans = INF
for i in product([0, 1], repeat=n):
    cost = 0
    smart = [0]*m
    for j in range(n):
        if i[j] == 0:
            continue
        c, *a = ca[j]
        cost += c
        for k in range(m):
            smart[k] += a[k]

    if all(x <= y for y in smart):
        ans = min(ans, cost)

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

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 np.any(tmp):
      if M == np.count_nonzero(tmp[1:] >= X):
        out = min(out, tmp[0])
if out == 10**18:
  print(-1)
else:
  print(out)

Solution (Python):


n, m, x = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(n)]
ans = 12 * (10 ** 5) + 1

for bit in range(2 ** n):
    tmp_book = [0] * m
    price = 0
    for i in range(n):
        if ((bit >> i) & 1):
            price += book[i][0]
            for j in range(m):
                tmp_book[j] += book[i][j + 1]
    if all(item >= x for item in tmp_book):
        ans = min(price, ans)

if ans != 12 * (10 ** 5) + 1:
    print(ans)
else:
    print(-1)

Solution (Python):
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,X = LI()
CA = np.array([LI() for _ in range(N)],dtype=int)
ans = float('INF')
for i in range(2**N):
    bit = np.array([[i>>j&1 for j in range(N)]]).T
    t = np.sum(CA*bit,axis=0)
    if np.all(t[1:]>=X):
        ans = min(ans,t[0])
print(ans if ans !=float('INF') else -1)

Solution (Python):

from itertools import combinations


def main(N,M,X,C, A):
    min_cost = ''
    combs = set()
    for i in range(N):
        for c in combinations(range(N), i+1):
            combs.add(c)

    for comb in combs:
        cost = 0
        xs = [0 for _ in range(M)]
        for c in comb:
            for i in range(M):
                xs[i] += A[c][i]
            cost += C[c]

        if all([x>=X for x in xs]):
            min_cost = cost if min_cost =='' else min(min_cost, cost)

    if min_cost != '':
        print(min_cost)
    else:
        print(-1)

    pass

if __name__ == '__main__':
    C = []
    A = []
    N, M, X = list(map(int, input().split()))
    for n in range(N):
        lst = list(map(int, input().split()))
        
        
        c = lst[0]
        a = lst[1:]

        C.append(c)
        A.append(a)

    
    main(N,M,X,C, A)