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 main():
    n,m,x = map(int,input().split())
    c = []
    for i in range(n):
        cc = list(map(int,input().split()))
        c.append(cc)
    tmp = 2 ** n
    ans = 10**8

    bi=str(format(tmp,"b"))
    for k in range(tmp):
        anstmp = 0
        ary = [0] * m
        for i in range(n):
            if ((k >> i) & 1):
                anstmp += c[i][0]
                for j in range(1,m+1):
                    ary[j-1] += c[i][j]

        
        flg = True
        for j in range(m):
            if ary[j] < x:
                flg = False
                break
        if anstmp < ans and flg:
            ans = anstmp
    if ans == 10**8:
        print(-1)
    else:
        print(ans)



if __name__=='__main__':
    main()

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

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

c=np.array(c)
a=np.array(a)

pat=2**n
ans=MAX
for i in range(pat):
    pat_i=bin(i)[2:].zfill(n)
    ai=np.array([0 for _ in range(m)])
    ansi=0

    for j in range(len(pat_i)):
        if(pat_i[j]=='1'):
            ansi+=c[j]
            ai+=a[j]

    if(min(ai)>=x):
        ans=min(ans,ansi)

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

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy





sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




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

    d = []
    for _ in range(n):
        d.append(na())

    ans = INF
    for i in range(2 ** n):
        score = [0 for _ in range(m + 1)]
        for j in range(n):
            if i >> j & 1:
                for k in range(m + 1):
                    score[k] += d[j][k]

        
        flg = True
        for j in range(1, m + 1):
            if score[j] < x:
                flg = False
                break
        if flg:
            ans = min(ans, score[0])

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,m,x=map(int,input().split())
    L=[list(map(int,input().split())) for i in range(n)]
    val=10**10

    
    
    for i in range(2 ** n):
        ans=[0]*m
        cnt=0
        for j in range(n):  
            if ((i >> j) & 1):  
                cnt+=L[j][0]
                for k in range(1,m+1):
                    ans[k-1]+=L[j][k]
        flag=True
        for l in range(m):
            if ans[l]<x:
                flag=False
                break
        if flag==True:
            val=min(val,cnt)
        
    if val==10**10:
        print(-1)
    else:
        print(val)
    

    
resolve()

Solution (Python):
from itertools import product

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

min_total = 10**10
for pattern in product([False, True], repeat=N):
    rikai = [0] * M
    total = 0
    for i, p in enumerate(pattern):
        if not p:
            continue
        for m in range(M):
            rikai[m] += A[i][m]
        total += C[i]

    if all(r >= X for r in rikai):
        min_total = min(total, min_total)

print(min_total if min_total < 10**10 else -1)

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

n = 1<<(N)
min_cost = 100000000
for one in range(n):
    tmp = [0]*M
    cost = 0
    for i in range(N):
        if (one>>i & 1)==1:
            cost+=CA[i][0]
            for j in range(M):
                tmp[j]+=CA[i][j+1]
    flag = True
    for i in range(M):
        if tmp[i]<X:
            flag=False
            break
    if flag:
        min_cost = min(min_cost, cost)
    
if min_cost == 100000000:
    print(-1)
else:
    print(min_cost)

Solution (Python):
def main():
  N, M, X = map(int, input().split())
  ans = float('inf')
  table = []
  for i in range(N):
    table.append(list(map(int, input().split())))
                 
  for i in range(2 ** N):
    tmp = [0] * (M+1)
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M+1):
              tmp[k] += table[j][k]
    for l in range(1, len(tmp)):
      if tmp[l] < X:
        break
    else:
      if ans > tmp[0]:
        ans = tmp[0]
  if ans != float('inf'):
    print(ans)
  else:
    print(-1)  
    
if __name__ == '__main__':
  main()

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def main():
    N, M, X_SUM = MI()
    C = [0] * N
    A = [None] * N

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

    ans = 10**19
    for i in range(1, N+1):
        for select_idx in combinations(range(N), i):
            X = [0] * M
            price = 0
            for book_idx in select_idx:
                for x_idx in range(M):
                    X[x_idx] += A[book_idx][x_idx]
                price += C[book_idx]

            if all([x >= X_SUM for x in X]):
                ans = min(ans, price)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 


n, m, x = map(int, input().split())
ans = [0 for _ in range(m)]
a = []
minv = 1
for i in range(n):
    a.append(list(map(int, input().split())))
    minv += a[i][0]
maxv = minv
for i in range(2**n):
    ans = [0 for _ in range(m)]
    cnt = 0
    for j in range(n):
        if ((i>>j)&1):
            for k in range(m):
                ans[k] += a[j][k+1]
            cnt += a[j][0]
    ok = True
    for j in range(m):
        if ans[j] < x:
            ok = False
    if ok and cnt < minv: minv = cnt

print(minv) if minv != maxv else print(-1)

Solution (Python):
import numpy as np
n,m,x = map(int,input().split())
ca = np.array([list(map(int,input().split())) for i in range(n)])

ans = 10**10
for i in range(2**(n+1)):
    abi = np.zeros(m+1)
    bin_str = format(i, '013b')
    
    for i in range(n):
        if bin_str[-i-1] == "1":
            abi += ca[i]
    if min(abi[1:]) >= x:
        ans = min(ans,abi[0])
        
if ans == 10**10:
    print(-1)
else:
    print(int(ans))

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

ans=float("inf")
for i in range(2**N):
  bin=format(i, 'b')[::-1]
  
  l=0
  F=[0]*M
  for j,b in enumerate(bin):
    if b=="1":
      l+=L[j][0]
      for k in range(M):
        F[k]+=L[j][k+1]
  
  flag=1
  for k in range(M):
    if F[k]<X:
      flag=0
  if flag:
    ans=min(l,ans)
if ans==float("inf"):
  print(-1)
else:
  print(ans)

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

ans = 10**10
for i in range(1<<n):
    use = []
    for bit in range(n):
        if i>>bit&1:
            use.append(bit)
    under = [0 for _ in range(m)]
    now = 0
    for j in use:
        for k,a in enumerate(data[j]):
            under[k] += a
        now += c[j]
    check = True
    for k in range(m):
        if under[k] < x:
            check = False
    if check:
        ans = min(ans, now)

print(ans if ans < 10**10 else -1)

Solution (Python):

n,m,x=map(int,input().split())
cost=[0]*n
l=[]
ans=-1
for i in range(n):
    l.append(list(map(int,input().split())))
for i in range(1<<n):
    skill=[0]*m
    cost=0
    bit=[(i>>j)&1 for j in range(n)]
    for j in range(n):
        if bit[j]==1:
            cost+=l[j][0]
            for k in range(m):
                skill[k]+=l[j][k+1]
    check=0
    for num in skill:
        if num<x:
            check=1
            break
    if check==0:
        if ans==-1:
            ans=cost
        else:
            ans=min(ans,cost)
print(ans)

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

m = 10**8
for i in range(1<<N):
    alg = [0]*M
    money = 0
    for j in range(N):
        if (i>>j)&1:
            money += CA[j][0]
            for k in range(M):
                alg[k] += CA[j][k+1]
    clear = True
    for k in range(M):
        clear = clear and alg[k]>=X
    if clear and money<m:
        m = money
if m == 10**8:
    m = -1
print(m)

Solution (Python):
n,m,x=(map(int,input().split()))
a=[]
ans=99999999999999999999999999
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(2**n+1):
    ta=0
    temp=[0]*m
    for j in range(n):
        if (i&(1<<j))!=0:
            ta+=a[j][0]
            for k in range(m):
                temp[k]+=a[j][k+1]
    flag=True
    
    for k in range(m):
        if temp[k]>=x:
            continue
        flag=False
        break
    if flag:
        ans=min(ta,ans)
if ans==99999999999999999999999999:
    print(-1)
else:
    print(ans)

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n,m,x=map(int,readline().split())
    c=[]
    a=[]
    for i in range(n):
        ca=list(map(int,readline().split()))
        c.append(ca[0])
        a.append(ca[1:])
    
    min_res=float("inf")
    for i in range(1<<n):
        output=[]
        res=0
        rikaido=[0]*m
        for j in range(n):
            if(i>>j)&1:
                output.append(j)
        for j in output:
            res+=c[j]
            for k in range(m):
                rikaido[k]+=a[j][k]
        for k in range(m):
            if rikaido[k]<x:
                break
        else:
            min_res=min(res,min_res)

    if min_res==float("inf"):
        min_res=-1

    print(min_res)
if __name__=="__main__":
    main()

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

for i in range(2**N):
    b=bin(i)[2:].zfill(N)
    t_cost=0
    for j in range(N):
        t_cost+=A[j][0]*int(b[j])
        for m in range(M):
            S[i][m]+=A[j][m+1]*int(b[j])
    
    if min(S[i])>=X:
        cost.append(t_cost)

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

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
import numpy as np
setrecursionlimit(10 ** 7)

n,m,x = map(int,stdin.readline().rstrip().split())
a = []
li = []
mi = 10**9
for i in range(n):
    lin = list(map(int,stdin.readline().rstrip().split()))
    a.append(lin[0])
    li.append(lin[1:])

li = np.array(li)

for i in range(2**n):
    lis = np.zeros(m)
    mil = 0
    for j in range(n):
        if ((i >> j) & 1):
            lis += li[j]
            mil += a[j]
    flag = True
    for k in lis:
        if k < x:
            flag = False
    if flag:
        mi = min(mi,mil)

if mi == 10**9:
    print(-1)
    exit()

print(mi)

Solution (Python):
import itertools 
from itertools import combinations, chain 
  
def findsubsets(s, n): 
    return list(map(set, itertools.combinations(s, n))) 


arr=[]
n,m,x=list(map(int,input().split(" ")))
book=[]
for i in range(n):
	temp=list(map(int,input().split(" ")))
	book.append(temp)
s=[]
for i in range(0,n):
	s.append(i)
elig=[]
for i in range(1,n+1):
	temp=findsubsets(s,i)
	
	for j in range(len(temp)):
		sub=temp[j]
		algo=[0]*m
		cost=0
		for k in sub:
			b=book[k]
			cost+=b[0]
			for l in range(1,len(b)):
				algo[l-1]+=b[l]

		fl=0
		for k in range(m):
			if(algo[k]<x):
				fl=1
				break
		if(fl==0):
			elig.append(cost)
if(len(elig)==0):
	print(-1)
else:
	print(min(elig))

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M, X = rl()
C = []
As = []
for i in range(N):
	A = rl()
	C.append(A[0])
	As.append(A[1:])

def is_ok(b):
	sums = [0] * M
	for j in range(M):
		for i, v in enumerate(b):
			if v == 0: continue
			sums[j] += As[i][j]
		if sums[j] < X:
			return False
	return True

def cost(b):
	c = 0
	for i, v in enumerate(b):
		if v == 0: continue
		c += C[i]
	return c

import itertools
ans = float('inf')
for b in itertools.product([0, 1], repeat = N):
	if is_ok(b):
		ans = min(ans, cost(b))
if ans == float('inf'):
	print(-1)
else:
	print(ans)

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

ans = []

K = 2 
for i in range(K**N):
    TF=[0]*N

    for j in range(N):
        TF[N-j-1] = i % K
        i //= K
    
    price = 0
    knowledge = [0]*M
    for j in range(N):
        if TF[j] == 1:
            price += C[j]
            for k in range(M):
                knowledge[k] += A[j][k+1]
        flag = 0
        for k in range(M):
            if knowledge[k] < X:
                flag = 1
        if flag == 0:
            ans.append(price)

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

Solution (Python):
import numpy as np

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

for i in range(2**N):
    C = np.array([0]*(M+1))
    for j in range(N):
        if ((i >> j) & 1):
            C += A[j]
    for j in range(1,M+1):
        if C[j] < X:
            break
    else:
        c = min(c,C[0])

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

Solution (Python):
n, m, x = map(int, input().split())
c = [None for _ in range(n)]
a = [None for i in range(n)]
ans = None
for i in range(n):
    c[i], *ai = map(int, input().split())
    a[i] = list(ai)
for p in range(2 ** n):
    y = [0 for _ in range(m)]
    s = format(p, '0{:}b'.format(n))
    cp = 0
    for i, (si, ci) in enumerate(zip(s, c)):
        if si == '1':
            cp += ci
            for j in range(m):
                y[j] += a[i][j]
    for yj in y:
        if yj < x:
            break
    else:
        ans = cp if ans is None else min(ans, cp)
if ans is None:
    print(-1)
else:
    print(ans)

Solution (Python):
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m,x=INTM()
    ca=[]
    for i in range(n):
        ca.append(LIST())
    inf=10**9
    ans=inf
    for i in range(2**n):
        bag=[]
        for j in range(n):
            if ((i>>j)&1):
                bag.append(ca[j])
        ms=[0]*(m+1)
        for k in bag:
            for l in range(1,m+1):
                ms[l]+=k[l]
        ms=ms[1:]
        flg=1
        
        for j in range(m):
            if ms[j]<x:
                flg=0
        if flg==1:
            cost=0
            for k in bag:
                cost+=k[0]
            ans=min(ans,cost)
    
    if ans==inf:
        print(-1)
    else:
        print(ans)
    
    
if __name__ == '__main__':
    do()

Solution (Python):
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m,x = mp()
cost = []
book = []
inf = int(1e18)
ans = inf
for i in range(n):
    c = lmp()
    cost.append(c[0])
    book.append(c[1:])
cond = [bin(i)[2:].zfill(n) for i in range(2**n)]
for i in range(len(cond)):
    cnt = 0
    al = [0]*(m)
    for j in range(n):
        if cond[i][j] == "1":
            cnt += cost[j]
            for k in range(m):
                al[k] += book[j][k]
    flag = True
    for j in range(m):
        if al[j] < x:
            flag = False
    if flag:
        ans = min(ans,cnt)
if ans == inf:
    print(-1)
else:
    print(ans)

Solution (Python):
from itertools import product


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

    it = (0, 1)
    pat = list(product(it, repeat=N))

    ans = 10**10
    for p in pat:
        tmp = [0] * M
        flag = [0] * M
        tmp_cost = 0
        for i, b in enumerate(p):
            if b == 1:
                tmp_cost += CA[i][0]
                for j in range(M):
                    tmp[j] += CA[i][j+1]
                    if tmp[j] >= X:
                        flag[j] = 1
                if sum(flag) == M:
                    if ans > tmp_cost:
                        ans = tmp_cost

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


if __name__ == "__main__":
    main()

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

A = []
C = []
for _ in range(N):
    c, *row = list(map(int, input().split()))
    C.append(c)
    A.append(row)

INF = float('inf')
result = INF
for bit in range(1 << N):
    cost = 0
    spec = [0 for _ in range(M)]
    for i in range(N):
        if (bit >> i) & 1:
            cost += C[i]
            for j in range(M):
                spec[j] += A[i][j]

    
    if min(spec) >= X:
        result = min(result, cost)

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

Solution (Python):
n,m,y=map(int,input().split())
List=[list(map(int,input().split())) for i in range(n)]
ans=10000000000
for i in range(2**n):
  money=0
  l=[0]*m
  for j in range(n):
    if (i>>j) & 1:
      money+=List[j][0]
      for x in range(m):
        l[x]+=List[j][x+1]
  if all(c>=y for c in l):
    if ans>money:
      ans=money
if ans==10000000000:
  print(-1)
else:
  print(ans)

Solution (Python):
def resolve():
    n, m, x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    ans = 10**8
    for i in range(2**n):
        book = [0] * n
        cost = 0
        lan = [0] * m
        for j in range(n):
            if (i >> j & 1):
                cost += c[j][0]
                for k in range(m):
                    lan[k] += c[j][k+1]
        ok = True
        for k in range(m):
            if lan[k] < x:
                ok = False
        if ok:
            ans = min(ans, cost)

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

resolve()

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

C=10**7

for i in range(1<<n):
    c=0
    R=[0]*m
    for j in range(n):
        if i&(1<<j):
            c+=L[j][0]
            for k in range(m):
                R[k]+=L[j][k+1]
    if min(R)>=x:
        C=min(c,C)

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

Solution (Python):

import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div

N, M, X = ri_()
C = [0] * N
A = []
for i in range(N):
    tmp = ri_()
    C[i] = tmp[0]
    A.append(tmp[1:])
ans = 10 ** 8
for bit in range(2 ** N):
    d = [0] * M
    cost = 0
    for i in range(N):
        if ((bit & (1 << i))):
            cost += C[i]
            for j in range(M):
                d[j] += A[i][j]
    f = 1
    for j in range(M):
        if d[j] < X:
            f = 0
    if f:
        ans = min(ans, cost)
if ans == 10**8:
    ans = -1
print(ans)

Solution (Python):





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

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

    min_total_cost = 10**9
    for i in range(2**N):
        total_cost = 0
        learned = [0] * M

        for j in range(N):
            if (i >> j) & 1:
                C, *As = books[j]
                total_cost += C

                for ids, a in enumerate(As):
                    learned[ids] += a

        if min(learned) >= X:
            min_total_cost = min(min_total_cost, total_cost)

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


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
N, M, K = map(int, input().split())
data = np.array([list(map(int, input().split())) for _ in range(N)])

costs = data[:, 0]
knows = data[:, 1:]

mincost = 1e+9
for i in range(2 ** N):
    bits = np.array([((i >> j) & 1) for j in range(N)])
    sumknows = (knows * bits[:, None]).sum(axis=0)
    if (sumknows >= K).all():
        cost = (costs * bits).sum()
        mincost = min(mincost, cost)
print(mincost if mincost < 1e+9 else -1)

Solution (Python):
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M, X = list(map(int,_in[0].split(' ')))  
    C_A_arr = []
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  
        C_A_arr.append(_)
    
    condition = [0]*M
    cnt = float('inf')
    for bit in range(1<<N):
        condition = [0]*M
        _cnt = 0
        for i in range(N):
            if bit&(1<<i):
                for j in range(M):
                    condition[j] += C_A_arr[i][j+1]
                _cnt += C_A_arr[i][0]
        if min(condition) >= X:
            cnt = min(cnt,_cnt)
    if cnt == float('inf'):
        cnt = -1
    
    print(cnt)

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

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


ans = float('inf')
for i in range(2**N):
    ac = [-1]*N
    total = [0]*M
    temp = 0
    flg = 0
    for j in range(N):
        if (i>>j)&1:
            ac[j] = 1
    for n in range(N):
        if ac[n]==1:
            temp += C[n]
            for m in range(M):
                total[m] = total[m] + A[n][m]
    for m in range(M):
        if total[m]<X:
            flg = 1
    if flg==0:
        ans = min(ans, temp)
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):


import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M, X = LI()
CA = LRI(N)

ans = INF
for bit in range(1 << N):
    Ms = [0] * M
    tmp = 0
    for i in range(N):
        if (bit >> i) & 1:
            for j in range(M):
                Ms[j] += CA[i][j+1]
            
            tmp += CA[i][0]
    
    flag = True
    for m in Ms:
        if m < X:
            flag = False
    
    if flag:
        ans = min(ans, tmp)

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

Solution (Python):
import itertools
n,m,x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
ans = 1000000000000
for i in range(2 ** n):
    skill = [0]*m
    cost = 0
    for j in range(n):
        if ((i>>j)&1):
            cost += c[j][0]
            for k in range(m):
                skill[k] += c[j][k+1]
 
                
    if (min(skill)>=x):
        if (ans > cost):
            ans = cost
if (ans != 1000000000000):
    print(ans)
else:
    print(-1)

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

minv = 10**8
for i in range(2 ** N):
    alg = [0]*M
    cost = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k, ca in enu(CA[j]):
                if k == 0:
                    cost += ca
                else:
                    alg[k-1] += ca
    if all([X<=val for val in alg]):
        if cost < minv:
            minv = cost

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

Solution (Python):
import sys
from itertools import combinations

import numpy as np

input = sys.stdin.readline


def main():
    N, M, X = map(int, input().split())
    C = [0] * N
    A = np.zeros(shape=(N, M), dtype=int)
    for i in range(N):
        CA = list(map(int, input().split()))
        C[i], A[i] = CA[0], CA[1:]

    ans = float("inf")
    for i in range(1, 13):
        for comb in combinations(range(N), i):
            total = 0
            B = np.zeros(shape=M, dtype=int)
            for j in comb:
                total += C[j]
                B += A[j]
            if all(b >= X for b in B):
                if total < ans:
                    ans = total

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
INF = 10**18

n, m, x = map(int, input().split())
costs = []
a = []
for i in range(n):
    cost, *tmp = map(int, input().split())
    costs.append(cost)
    a.append(tmp)

ans = INF
for i in range(1 << n):
    cost = 0
    ms = [0] * m
    for j in range(n):
        if (i >> j) & 1 == 1:
            cost += costs[j]
            for k in range(m):
                ms[k] += a[j][k]
    can_learn = True
    for j in range(m):
        if ms[j] < x:
            can_learn = False
            break
    if can_learn:
        ans = min(ans, cost)

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

Solution (Python):
n,m,co=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(map(int,input().split())))
c=2**n
ans=10**10
for i in range(c):
  li=[]
  a=0
  for j in range(n):  
      if ((i >> j) & 1):  
        li.append(l[j])
        a+=l[j][0]
  z=[0]*m
  for k in range(len(li)):
    for kk in range(m):
      z[kk]+=li[k][kk+1]
  if min(z)>co-1:
    ans=min(ans,a)
if ans==10**10:
  print(-1)
else:
  print(ans)

Solution (Python):
n,m,x = map(int,input().split())
all_cand = []
for i in range(2**n):
  p_m_list = [False for i in range(n)]
  for j in range(n):
    if ((i >>j) & 1):
      p_m_list[j] = True
  all_cand.append(p_m_list)
c_list = []
for i in range(n):
  c_list.append(list(map(int,input().split())))
result_list = []
for cand in all_cand:
  count = 0
  a_list = [0 for i in range(m)]
  for i in range(len(cand)):
    if cand[i] == True:
      count += c_list[i][0]
      for j in range(1,m+1):
        a_list[j-1] += c_list[i][j]
  if min(a_list) >= x:
    result_list.append(count)
if len(result_list) == 0:
  print(-1)
else:
  print(min(result_list))