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):
import itertools
import numpy as np
N, M, X = map(int, input().split())

book = []
for _ in range(N):
    tmp = [int(i) for i in input().split()]
    book.append(tmp)




lis = list(range(N))
result = []
for n in range(1, len(lis)+1):
    for conb in itertools.combinations(lis, n):
        result.append(list(conb))  


ans = []

for com in result:
    
    l = len(com)
    s_skill = np.array([0] * M)
    money = 0
    for idx in com:
        money += book[idx][0]
        s_skill += np.array(book[idx][1:])

    flg = True
    for i in s_skill:
        if i < X:
            flg = False
    ans.append([flg, money])



output = -1
b_flg = False
for i in ans:
    b = i[0]
    money = i[1]
    if b:
        b_flg = True
        if output == -1:
            output = money
        output = min(output, money)

if not b_flg:
    print(-1)
else:
    print(output)

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

lis = []
for i in range(n):
  li = list(map(int, input().split()))
  lis.append(li)
  
anss = [0]*2**n
for i in range(2**n):
  rikaido = [0]*m
  for j in range(n+1):
    if str(bin(i)[-j-1]) == "1":
      anss[i] += lis[j][0]
      for k in range(m):
        rikaido[k] += lis[j][k+1]
    elif str(bin(i)[-j-1]) == "b":
      for k in range(m):
        if rikaido[k] < x:
          anss[i] = 0
      break

ans = 10**10
for i in range(2**n):
  if anss[i] > 0:
    ans = min(ans, anss[i])

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

Solution (Python):
from itertools import product

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

a = []
c = []

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

ans = []
for b in product([0, 1], repeat=N):
    total = 0
    lrn = [0] * M
    for k, i in enumerate(b):
        total += i * c[k]
        for j in range(M):
            lrn[j] += a[k][j]*i

    if min(lrn) >= X:ans.append(total)
print(-1 if ans==[] else min(ans))

Solution (Python):
N,M,X=map(int,input().split())
ans=[]
c=[]
for _ in range(N):
    c.append(list(map(int, input().split())))
for i in range(pow(2,N)):
    d=[0]*(M+1)
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M+1):
                d[k]+=c[j][k]
    j=True
    for l in range(1,M+1):
        if d[l]<X:
            j=False
    if j:
        ans.append(d[0])
if len(ans)!=0:
    print(min(ans))
else:
    print(-1)

Solution (Python):
cin = open(0).read().strip().split('\n')
n,m,x = map(int, cin[0].split(' '))
books = []
for i in cin[1:]:
    books.append(tuple(map(int, i.split(' '))))

money = float('inf')
for i in range(2**n):
    ret = [0] * m
    tmp_money = 0
    for j in range(n):
        if i >> j & 1:
            for mi in range(m):
                ret[mi] += books[j][1+mi]
            tmp_money += books[j][0]
    if min(ret) >= x:
        money = min(money, tmp_money)

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

Solution (Python):
n,m,x = map(int,input().split())
goods = [list(map(int,input().split())) for i in range(n)]
from itertools import combinations as comb
minm=float('INF')
def check(l):
    suml = [0]*(m+1)
    for j in l:
        good = goods[j]
        for s in range(0,m+1):
            suml[s] += good[s]
    for j in range(1,m+1):
        if(suml[j]<x):
            return None
    return suml[0]

ok = False
for i in range(1,n+1):
    
    for l in comb(range(n),i):
        num = check(l)
        if(num is None):
            continue
        if(minm>num):
            minm = num
            ok = True
if(ok):
    print(minm)
else:
    print(-1)

Solution (Python):
from sys import stdin
import itertools
n,m,x = [int(x) for x in stdin.readline().rstrip().split()]
a = []
for i in range(n):
    a.append([int(x) for x in stdin.readline().rstrip().split()])
k = list(itertools.product(range(0,2), repeat=n))
ans = -1
for i in range(len(k)):
    b = [0]*m
    money = 0
    o = 1
    for j in range(n):
        if k[i][j] == 1:
            for l in range(m):
                b[l] += a[j][l+1]
            money += a[j][0]
    for j in range(m):
        if b[j] < x:
            o = 0
            break
    if o == 1:
        if ans == -1:
            ans = money
        else:
            ans = min(ans,money)
print(ans)

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

ans = []

for i in range(2 ** n):
    jud = [0]*m
    money = 0
    for j in range(n):
        if (i >> j) & 1:
            money += ca[j][0]
            for k in range(m):
                jud[k] += ca[j][k+1]
    if min(jud) >= x:
        ans.append(money)

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

Solution (Python):


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

    def calc(bit):
        i = 0
        rikai = [0] * M
        cost = 0
        while bit > 0:
            if bit & 1:
                cost += C[i]
                for j in range(M):
                    rikai[j] += A[i][j]
            bit = bit >> 1
            i += 1
        if all(r >= X for r in rikai):
            return cost
        else:
            return None

    bit = 1
    ans = float("inf")
    while bit <= (2**N-1):
        cost = calc(bit)
        if cost is not None:
            ans = min(ans, cost)
        bit += 1
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    main()

Solution (Python):
import numpy as np

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

ans = 13*10**5
for b in range(2**n):
    bit=[0]*n
    for i in range(n):      
        bit[i]=b%2
        b//=2 
    bit = np.array(bit).astype(bool)
    if bit.sum()==0:
      continue
    score = book[bit].sum(axis=0)
    if (score[1:] < x).sum() == 0:
      if ans > score[0]:
        ans = score[0]
if ans == 13*10**5:
  ans = -1
print(ans)

Solution (Python):

import numpy as np
import itertools


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

  INT_MAX = 100000000
  min_c = INT_MAX
  for conds in itertools.product([0, 1], repeat=N):
    result = np.dot(conds, mat)
    skills = result[1:]
    if np.all(skills >= X):
      min_c = min(min_c, result[0])

  print(min_c if min_c < INT_MAX else -1)


if __name__ == '__main__':
  main()

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

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

book_list.sort(key=lambda el: el[0])  


ans = 1e10

for bit in range(1 << n):
    
    algo_val = [0 for _ in range(m)]
    
    ans_tmp = 0

    
    for i, book in enumerate(book_list):
        if (bit & (1 << i)):
            ans_tmp += book[0]
            for j, a in enumerate(book[1:]):
                algo_val[j] += a

    if all(i >= x for i in algo_val):
        
        ans = min(ans_tmp, ans)

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

Solution (Python):
import numpy as np
n,m,x =map(int,input().split())
syo = []
for _ in range(n):
    temp =list(map(int,input().split()))
    syo.append(temp)

ans = []

for i in range(2 ** n):
    total = 0
    temp = [0]*m    
    for j in range(n):  
        if ((i >> j) & 1): 
            total += syo[j][0]
            for k in range(1,m+1):
                temp[k-1] += syo[j][k]
    if all(t >= x for t in temp):
        ans.append(total)

if ans:
    print(min(ans))
else:
    print("-1")

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

q = set()
q.add(tuple([0] * (m+1)))

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

    update = set()
    for qq in q:
        l = list(qq)
        l[0] = qq[0] + c[0]
        for i in range(1, m+1):
            l[i] = min(qq[i] + c[i], x)
        update.add(tuple(l))

    q.update(update)

max_ans = 10 ** 5 * 13
ans = max_ans
for qq in q:
    if qq[0] < ans and sum(qq[1:]) == m * x:
        ans = qq[0]

if ans < max_ans:
    print(ans)
else:
    print(-1)

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

ans=10000000000000000000000000000

for dummy in range(2**n):
  books=format(dummy, 'b')
  books='0'*(n-len(books))+books
  point=[0]*(m+1)
  cost=0
  for i in range(n):
    if books[i]=='1':
      cost+=cx[i][0]
      for j in range(1,m+1):
        point[j]+=cx[i][j]
  ok=1
  for j in range(1,m+1):
    if point[j]<x:
      ok=0
  if ok:
    ans=min(ans,cost)


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

Solution (Python):

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

result = -1
for i in range(2**n):
    rikai = [0]*m
    cost = 0
    
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m):
                rikai[k] += a[j][k+1]
            cost += a[j][0]
        
    satisfied = True
    for rj in rikai:
        if rj < x:
            satisfied = False
            break

    if result == -1:
        if satisfied:
            result = cost
    else:
        if satisfied & (cost<result):
            result = cost

print (result)

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

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

minyen = float("inf")
for i in range(2**N):
    flag = False
    hoji = []
    rikai = [0]*M
    
    for j in range(N):
        if((i>>j)&1):
            hoji.append(hon[j][0])  
            for k in range(M):
                rikai[k] += hon[j][k+1]

    for k in range(M):
        if X > rikai[k]:
            flag = True
            break

    if flag:
        continue
    else:
        minyen = min(minyen,sum(hoji))

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

Solution (Python):
import itertools
import numpy as np
N,M,X=map(int,input().split())
CA=[]
for i in range(N):
  CA.append(list(map(int,input().split())))
money=9000000000
count=1
for i in range(1,N+1):
  test=itertools.combinations(CA,i)
  for j in test:
    pre_ans=np.sum(j, axis=0)
    if pre_ans[0]<money and np.all(pre_ans[1:]>=X):
      money=pre_ans[0]
      count=0
if count==0:
  print(money)
else:
  print(-1)

Solution (Python):
n,m,x=map(int,input('').split(' '))
c=[]
a=[]
for k in range(n):
    s=input('')
    s=s.split(' ')

    c.append(int(s[0]))
    kara=[]
    for l in range(len(s)-1):
        kara.append(int(s[l+1]))
    
    a.append(kara)

b=[]
for k in range(n):
    b.append(0)

lx=[]
for k in range(m):
    lx.append(0)

able=0
mcos=100000000000000000
while b[n-1]!=2:
    cost=0

    for k in range(m):
        lx[k]=0
    
    for k in range(n):
        if b[k]==1:
            for j in range(m):
                lx[j]+=a[k][j]
            cost+=c[k]
    
    ok=1
    for k in range(m):
        if lx[k]>=x:
            ok=ok*1
        else:
            ok=ok*0
        
    if ok==1 and cost<=mcos:
        able=1
        mcos=cost
    
    b[0]+=1
    for k in range(n-1):
        if b[k]==2:
            b[k]=0
            b[k+1]+=1

if able==1:
    print(mcos)
else:
    print(-1)

Solution (Python):


import sys












from itertools import product, permutations  









def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m, x = mi()
    cost = []
    effect = []
    for _ in range(n):
        line = lmi()
        cost.append(line[0])
        effect.append(line[1:])

    ans = 10 ** 10
    for p in product([True, False], repeat=n):    
        price = 0
        improved = [0] * m
        for i in range(len(p)):    
            if p[i]:
                price += cost[i]
                for j in range(len(effect[i])):    
                    improved[j] += effect[i][j]
        
        
        
        if all(map(lambda imp: imp >= x, improved)):
            ans = min(ans, price) 
            
    print(ans) if ans != 10**10 else print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations
from sys import stdin


def main():
    N, M, X = [int(x) for x in stdin.readline().rstrip().split()]
    CAs = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
    ans = 100100100100100
    for n in range(1, N + 1):
        for comb in combinations(range(1, N + 1), n):
            tmp = [0] * (M + 1)
            for c in comb:
                for i in range(len(tmp)):
                    tmp[i] += CAs[c - 1][i]
            if len([x for x in tmp[1:] if X <= x]) == M:
                ans = min(ans, tmp[0])
    if ans == 100100100100100:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product
n, m, x = map(int, input().split())
books = [[int(j) for j in input().split()] for i in range(n)]
min_cost = float('inf')
for bit in product([0, 1], repeat=n):
    cost = 0
    skill = [0] * m
    for i, b in enumerate(bit):
        if b == 1:
            cost += books[i][0]
            for j in range(m):
                skill[j] += books[i][j + 1]
    if x <= min(i for i in skill):
        min_cost = min(min_cost, cost)
print(min_cost if min_cost != float('inf') else -1)

Solution (Python):

"""
Created on Sun May 10 21:06:30 2020

@author: shinba
"""
n,m,x = map(int,input().split())

ca = []
for i in range(n):
    ca.append(list(map(int,input().split())))
    
ans = float("inf")
for i in range(1,2**n):
    s = [0]*(m+1) 
    for j in range(n):
        if (i>>j) & 1:
            s[0] += ca[j][0]
            for k in range(1,m+1):
                s[k] += ca[j][k]
    if s[0] < ans:
        for i in range(1,m+1):
            if s[i] < x:
                break
        else:
            ans = s[0]

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

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

costs = [0]*n
values = []

for i in range(n):
    v = list(map(int, input().split()))
    costs[i] = v[0]
    values.append(v[1:])

candidates = []
for i in range(pow(2, n)):

    learning = [0]*m
    currentCost = 0
    for bit in range(n):
        select = i >> bit & 1
        if select == 1:
            currentCost += costs[bit]
            for j, v in enumerate(values[bit]):
                learning[j] += v

    if all([l >= x for l in learning]):
        candidates.append(currentCost)

print((-1 if len(candidates) == 0 else min(candidates)))

Solution (Python):
from itertools import combinations

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

ans = -1

for j in range(1, N+1):
    for i in combinations(box, j):
        kakaku = 0
        rika = [0 for _ in range(M)]
        for el in i:
            kakaku += el[0]
            for n, k in enumerate(el[1:]):
                rika[n] += k

        if all(p >= X for p in rika):
            if ans == -1:
                ans = kakaku
            else:
                ans = min(kakaku, ans)

print(ans)

Solution (Python):
import itertools
import numpy as np
def main():

    n,m,x = tuple([int(t)for t in input().split()])

    a = [np.array([int(t)for t in input().split()])for _ in [0]*n]
    candidate = []
    for i in range(n):
        for data in itertools.combinations(a,i+1):
            data = sum(data)
            if np.all(data[1:]>=x):
                candidate.append(data[0])
    if len(candidate)==0:
        print(-1)
    else:
        print(min(candidate))


if __name__ == "__main__":
    main()

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

C=[]
A=[]
for i in range(N):
    tCA=list(map(int,input().split(' ')))
    C.append(tCA[0])
    A.append(tCA[1:M+1])
maxCost=10**8
minCost=maxCost


for i in range(2**N):
    binstr=format(i,'0'+str(N)+'b')
    
    tmpM=[]
    for t in range(M):
        tmpM.append(0)
    tmpCost=0
    for n in range(N):
        if binstr[n]=='1':
            tmpCost+=C[n]
            for m in range(M):
                
                tmpM[m]+=A[n][m]
    
    
    
    flg = True
    for m in range(M):
        if tmpM[m] < X:
            flg=False
    if flg:
        minCost=min(minCost,tmpCost)

if minCost==maxCost:
    print(-1)
else:
    print(minCost)

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

ans=[]
for i in range(2**n):
	A=[0]*m
	C=0
	lst=list(map(int,format(i,'b').zfill(n)))
	for j in range(n):
		if lst[j]==1:
			C+=c[j]
			for k in range(m):
				A[k]+=a[j][k]
	if all(elem>=x for elem in A):
		ans.append(C)
if len(ans):
	print(min(ans))
else:
	print(-1)

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

bestcost = 9999999999
for i in range(pow(2,n)):
    ability = [0]*m
    cost = 0
    num = i
    k = n-1
    while k >= 0:
        if num // pow(2,k) == 1:
            cost += books[k][0]
            for j in range(m):
                ability[j] += books[k][j+1]
            num -= pow(2,k)
        k -= 1
    
    for j in range(m):
        if ability[j] < x:
            cost = 9999999999
    bestcost = min(cost, bestcost)
    

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

Solution (Python):
import numpy as np
n,m,x=map(int,input().split())
ans=10**10
f=1
s=[list(map(int,input().split())) for _ in range(n)]
for i in range(1<<n):
  t=np.zeros(m+1)
  for j in range(n):
    if (i>>j)&1:
      t=t+np.array(s[j])
  if all(t[1:]>=x):
    ans=min(t[0],ans)
    f=0
if f:
  print(-1)
else:
  print(int(ans))

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

cost = []
for i in range(2**N):
    cst = 0
    alg = [0 for _ in range(M)]
    Flg = True
    for j in range(N):
        if((i >> j) & 1):
            cst += lst[j][0]
            for k in range(1, M+1):
                alg[k-1] += lst[j][k]
    
    for a in alg:
        if(a < X):
            Flg = False
    if(Flg):
        cost.append(cst)
    
if(len(cost) > 0):
    print(min(cost))
else:
    print(-1)

Solution (Python):



import sys
import numpy as np
input = sys.stdin.readline





n,m,x = map(int,input().split())
A = np.array([list(map(int,input().split())) for _ in range(n)])
ans = 10**8
for i in range(1,2 ** n):
    bag = np.array([])
    total = 0
    for j in range(n):  
        if ((i >> j) & 1):  
              
            total += A[j]
            
              

    if x <= min(list(total[1::])):
        ans = min(ans , total[0])

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

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

a = []

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

a = np.array(a)

lis = list(itertools.product([0,1],repeat=n))
mon = [10**8 for i in range(n)]
mi = 10**8

for i in lis:
    sum = [0 for _ in range(m+1)]
    hantei = 0
    for ind,j in enumerate(i):
        if j==1:
            sum += a[ind]

    for m in range(1,m+1):
        if sum[m]<x:
            hantei = 1
    if hantei == 0:
        mi = min(mi,sum[0])
if mi == 10**8:
    print(-1)
else:
    print(mi)

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


n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]
n_idx = [i for i in range(1, n+1)]
price_lst = []
for i in range(1, n+1):
    idx_lst = list(combinations(n_idx, i))
    for idx_tup in idx_lst:
        ans = np.array([0] * m)
        price = 0
        for idx in idx_tup:
            ans += np.array(ca[idx-1][1:])
            price += ca[idx-1][0]
        if all(ans >= x):
            price_lst.append(price)
if len(price_lst) > 0:
    print(min(price_lst))
else:
    print(-1)

Solution (Python):









import numpy as np






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

ans = 10**5 * N +1
for bitlines in range(0,1<<N):
    tmp = np.array([0]*(M+1))
    for target in range(N):
        if bitlines>>target & 1:
            tmp = tmp + rows[target]
        else:
            continue
    if np.bincount((tmp>=X)[1:],minlength=2)[1]==M:
        ans = min(ans,tmp[0])

if ans == 10**5 * N +1:
    ans = -1

print(ans)

Solution (Python):
import itertools
import copy
n,m,x = map(int,input().split())
ans = [0 for i in range(m)]
books = []
answer = 1000000000000000000000
for i in range(n):
    books.append(list(map(int,input().split())))
for i in range(n):
    stock = list(list(itertools.combinations([num for num in range(n)], i+1)))
    for j in stock:
        cost = 0
        ans = [0 for i in range(m)]
        for k in j:
            for e,l in enumerate(books[k]):
                if e == 0:
                    cost += l
                else:
                    ans[e-1] += l
            if min(ans) >= x and cost < answer:
                answer = copy.deepcopy(cost)
if answer == 1000000000000000000000:
    print(-1)
else:
    print(answer)

Solution (Python):
import itertools
n, m, x = map(int, input().split())
list_CA = [ list(map(int,input().split(" "))) for i in range(n)]
l = [i for i in range(1, n+1)]
ans = pow(10, 9)
for i in range(1, n+1):
    k = list(itertools.combinations(l, i))
    for j in range(len(k)):
        h = [0]*m
        cnt = 0
        for q in k[j]:
            for g in range(m):
                h[g] += list_CA[q-1][g+1]
            cnt += list_CA[q-1][0]
        c = 0
        for v in h:
            if v >= x:
                c += 1
        if c == m:
            ans = min(cnt, ans)

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

Solution (Python):
"""
learn M algorithms
all start at level 0
N books on algorithms
i-th book sold for C_i yen
understanding increase by A_i_j where j is the j-th algorithm

Goal: X or higher understanding for all M algorithms
MINIMIZE YEN USED
"""

def x_satisfied(cur_und, x):
    for val in cur_und:
        if val < x:
            return False
    return True

def copy_update(cur_und, matrix, item_num):
    cur_und = cur_und[::]

    for i, lvl in enumerate(matrix[item_num]):
        cur_und[i] += lvl
    
    return cur_und




def solve(n, m, x, cost, matrix):
    def rec_solve(item_num, cur_cost, cur_und):
        nonlocal cost, matrix, n, m, x

        if x_satisfied(cur_und, x):
            return cur_cost
        elif item_num == n:
            return float("inf")
        
        
        
        take = rec_solve(item_num + 1, cur_cost + cost[item_num], copy_update(cur_und, matrix, item_num))
        dont = rec_solve(item_num + 1, cur_cost, cur_und)

        return min(take, dont)

    return rec_solve(0,0, [0] * m)


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

for _ in range(N):
    row = []
    inp = map(int, input().split())
    cost.append(next(inp))
    for i in inp:
        row.append(i)
    matrix.append(row)

res = solve(N, M, X, cost, matrix)
if res == float("inf"):
    print(-1)
else:
    print(res)

Solution (Python):


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

import numpy as np
Cs = np.array([ca[0] for ca in CAs])
As = [np.array(ca[1:]) for ca in CAs]

import itertools
states = list(itertools.product([True, False], repeat=N))

def compute(state):
    arr = np.array([0] * M)
    for i in range(N):
        arr += As[i] * state[i]
    price = (Cs * state).sum() if ((arr >= X).sum() == M) else -1
    return price


res = np.array(list(map(compute, states)))
res = res[res > 0]
print(min(res) if len(res) > 0 else -1)

Solution (Python):
import numpy as np

N, M, X = [int(x) for x in input().split()]
books = []
ans = 10 ** 7
for i in range(N):
  books.append([int(x) for x in input().split()])
books = np.array(books)
for i in range(1,2**N):
  t = np.array([0]*(M+1))
  for j in range(N):
    if i & 1 == 1:
      t = t + books[j]
    i = i >> 1
  s = min(t[1:])
  if min(t[1:]) >= X:
    if t[0] < ans:
      ans = t[0]
  
if ans == 10 ** 7:
  print(-1)
else:
  print(ans)

Solution (Python):


import itertools
import numpy as np
N, M, X = map(int, input().split())
CA = np.zeros((N, M+1), dtype=np.int64)
for i in range(N):
    CA[i] = list(int(x) for x in input().split())

ans = 10**18
for lst in itertools.product((0,1), repeat=N):
    tmp = 0
    pnt = np.zeros(M, dtype=np.int64)
    for i in range(N):
        if lst[i] == 1:
            tmp += CA[i][0]
            pnt += CA[i][1:]
            if np.all(pnt >= X):
                ans = min(ans, tmp)

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

Solution (Python):

import itertools

N, M, X = map(int, input().split(' '))
books = []
ans = (10 ** 5) * N + 1

maximum = [0 for _ in range(M)]
book_id = [idx for idx in range(N)]

for _ in range(N):
    tmp = list(map(int, input().split(' ')))
    books.append(tmp)
    for idx in range(len(maximum)):
        maximum[idx] += tmp[idx+1]

for mx in maximum:
    if mx < X:
        print('-1')
        exit(0)

for book_num in range(1, N+1):
    combs = list(itertools.combinations(book_id, book_num))
    for comb in combs:
        ab = [0 for _ in range(M)]
        s = 0
        flag = True
        for el in comb:
            s += books[el][0]
            ab = [x + y for (x, y) in zip(ab, books[el][1:])]
        for el in ab:
            if el < X:
                flag = False
        if flag and s < ans:
            ans = s

print(ans)

Solution (Python):
import numpy as np

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

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

costs = []

for i in range(2**n):
  temp_cost = 0
  skill = np.zeros(m)
  for j in range(n):
    if i&1<<j:
      temp_cost += CA[j][0]
      skill += np.array(CA[j][1:])
      
  if all(skill>=x):
    costs.append(temp_cost)
    
if costs:
  print(min(costs))
else:
  print(-1)

Solution (Python):
from itertools import combinations


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

mtable = [None]*N
cs = []
for n in range(N):
    aa = list(map(int,input().split()))
    c = aa.pop(0)
    cs.append(c)
    ms = aa
    mtable[n] = ms
    


idxes = list(range(N))

prices = []
for i in range(1, N+1):
    for c in combinations(idxes, i):
        sums = [0]*M
        for idx in c:
            for i, m in enumerate(mtable[idx]):
                sums[i] += m
        if all(map(lambda x:x >= X, sums)):
            price = 0
            for idx in c:
                price += cs[idx]

            prices.append(price)
if prices == []:
    print(-1)
else:
    print(min(prices))

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

books = []
for i in range(n):
  line = input().split()
  book = [int(line[0])]
  for j in range(1, m + 1):
    book.append(int(line[j]))
  books.append(book)


prices = []
for p in range(2 ** n):
  u = [0] * m
  p_str = format(p, 'b').zfill(n)
  price = 0
  for k in range(len(p_str)):
    if p_str[k] == '1':
      price += books[k][0]
      for j in range(m):
        u[j] += books[k][j + 1]
  if min(u) >= x:
    prices.append(price)

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

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

lis = ["0"*(N-len(format(i,"b")))+format(i,"b") for i in range(1,2**N)]

minimam = 10**9

for i in lis:
    tmp = [0] *(M+1)
    flag = 0
    
    for j in range(len(i)):
        if i[j] == "1":
            for k in range(M+1):
                tmp[k] += books[j][k]
    for k in range(1,M+1):
        if tmp[k] < X:
            flag = 1
            break
    if flag == 0:
        minimam = min(minimam,tmp[0])

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

Solution (Python):
import numpy as np
import itertools

n, m, x = map(int, input().split())
table = [[0 for i in range(m+1)] for j in  range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(m+1):
        table[i][j] = tmp[j]
        
table = np.array(table)

ans = float('inf')
for i in range(1, n+1):
    choices = list(itertools.combinations(range(n), i))
    for choice in choices:
        score = np.array([0 for i in range(m+1)])
        for c in choice:
            score += table[c]
        if all(score[1:] >= x):
            ans = min(ans, score[0])
            
if ans == float('inf'):
    ans = -1
print(ans)