Problem:
 Score : 300 points    Problem Takahashi, who is a novice in competitive programming, wants to learn M algorithms.
Initially, his understanding level of each of the M algorithms is 0 .  Takahashi is visiting a bookstore, where he finds N books on algorithms.
The i -th book ( 1\leq i\leq N ) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j -th algorithm will increase by A_{i,j} for each j ( 1\leq j\leq M ).
There is no other way to increase the understanding levels of the algorithms.  Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.      Constraints  All values in input are integers.  1\leq N, M\leq 12  1\leq X\leq 10^5  1\leq C_i \leq 10^5  0\leq A_{i, j} \leq 10^5         Input Input is given from Standard Input in the following format:  N  M  X  C_1  A_{1,1}  A_{1,2}  \cdots  A_{1,M}  C_2  A_{2,1}  A_{2,2}  \cdots  A_{2,M}  \vdots  C_N  A_{N,1}  A_{N,2}  \cdots  A_{N,M}       Output If the objective is not achievable, print -1 ; otherwise, print the minimum amount of money needed to achieve it.        Sample Input 1 3 3 10
60 2 2 4
70 8 7 9
50 2 3 9      Sample Output 1 120  Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.       Sample Input 2 3 3 10
100 3 1 4
100 1 5 9
100 2 6 5      Sample Output 2 -1  Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.       Sample Input 3 8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2      Sample Output 3 1067

Solution (Python):
n, m, x = map(int, input().split())
costs = []
skills = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    cost = tmp[0]
    skill = tmp[1:]
    costs.append(cost)
    skills.append(skill)


min_cost = float("inf")
for i in range(1 << n):
    cur_skill = [0] * m
    cur_cost = 0
    for j in range(n):
        if (i >> j & 1) == 1:
            cur_cost += costs[j]
            for k in range(m):
                cur_skill[k] += skills[j][k]
    flag = True
    for j in range(m):
        if cur_skill[j] < x:
            flag = False
    if flag:
        min_cost = min(min_cost, cur_cost)

min_cost = -1 if min_cost == float("inf") else min_cost
print(min_cost)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import product
def main():
    n,m,x=map(int,input().split())
    CA=[[int(_) for _ in input().split()] for i in range(n)]
    ans=10**10
    n_lis=list(product([True,False],repeat=n))
    for comb in n_lis:
        cunt=0
        A=[0]*m
        for i,ca in enumerate(CA):
            if comb[i]:
                cunt+=ca[0]
                for j,aa in enumerate(ca[1:]):
                    A[j]+=aa
        for a in A:
            if a<x:
                break
        else:
            ans=min(ans,cunt)
    if ans==10**10:
        print(-1)
    else:
        print(ans)

if __name__=='__main__':
    main()

Solution (Python):
N, M, X = list(map(int, input().split()))
costs = []
As = []
for i in range(N):
    t = list(map(int, input().split()))
    costs.append(t[0])
    As.append(t[1:])
ans = -1
for i in range(2 ** N):
    tot = [0] * M
    cost = 0
    for j in range(N):
        if i >> j & 1:
            cost += costs[j]
            for k in range(M):
                tot[k] += As[j][k]
        flag = True
        for k in range(M):
            if tot[k] < X:
                flag = False
        if flag:
            if ans < 0:
                ans = cost
            else:
                ans = min(ans, cost)
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n,m,x=map(int,input().split())
c=[]
a=[]
for _ in range(n):
	s,*t=map(int,input().split())
	c.append(s)
	a.append(t)
ans=float("inf")
for i in range(2**n):
	l=[[0]*m]
	need=0
	for j in range(n):
		if i&(1<<j):
			l.append(a[j])
			need+=c[j]
	if all(sum(t)>=x for t in zip(*l)):
		ans=min(ans,need)
print(ans if ans!=float("inf") else -1)

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

cand = []
for i in range(2 ** n):
    text = []
    for j in range(n):
        if ((i >> j) & 1):
            text.append(j)
    cand.append(text)

ret = 10 ** 100

for item in cand:
    kakaku = 0
    rikai = [0] * m
    for val in item:
        kakaku += mtx[val][0]
        for j in range(1, m+1):
            rikai[j-1] += mtx[val][j]
    is_ok = True
    for val in rikai:
        if val < x:
            is_ok = False
            break
    if is_ok:
        ret = min(ret, kakaku)

if ret == 10 ** 100:
    print(-1)
else:
    print(ret)

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

ans=10**10
for n in range(2**N):
  bit=format(n,'0'+str(N)+'b')
  bit=list(map(int,bit))
  nedan=0
  tmp=[0]*M
  for a,c,b in zip(A,C,bit):
    if b==0:continue
    nedan+=c
    for i in range(M):
      tmp[i]+=a[i]
  if min(tmp)>=X and nedan<ans:
    ans=nedan
if ans==10**10:
  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):
    t = [int(x) for x in input().split()]
    C[i] = t[0]
    A[i] = t[1:]

ans = float("inf")
for bit in range(2**N):
    score = [0] * M
    cost = 0
    for i in range(N):
        if (bit >> i) & 1:
            cost += C[i]
            for j in range(M):
                score[j] += A[i][j]

    is_ok = True
    for i in range(M):
        if score[i] < X:
            is_ok = False

    if is_ok:
        ans = min(ans, cost)

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

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

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

result = -1
for i in range(1 << N):
    t = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        a = A[j]
        for k in range(M):
            t[k] += a[k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Solution (Python):
inf = 10**15
mod = 10**9+7

n,m,x = map(int, input().split())
san = [list(map(int, input().split())) for i in range(n)]
ans = inf
for i in range(2**n):
    cost = 0
    judge = [0 for i in range(m)]
    for j in range(n):  
        if ((i >> j) & 1):  
            for k in range(m):
                judge[k] += san[j][k+1]
            cost+=san[j][0]
    flag = True
    for l in range(m):
        if judge[l] < x:
            flag = False
            break
    if flag:
        ans = min(ans,cost)
if ans == inf:
    print(-1)
else:
    print(ans)

Solution (Python):
N, M, X = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = float('inf')
for i in range(2 ** N):
    tmp = [0]*M
    tmp_ans = 0
    for k in range(N):
        if 1 & i>>k:
            for l in range(1,M+1):
                tmp[l-1] += arr[k][l]
            tmp_ans += arr[k][0]
    flg = True
    for k in tmp:
        if k < X:
            flg = False
            break
    if flg:
        ans = min(ans,tmp_ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
n,m,x=map(int,input().split())
book=[]
ans=float("inf")
for _ in range(n):
    b=list(map(int,input().split()))
    book.append(b)

for bit in range(1,2**n+1):
    al=[0 for _ in range(m+1)]
    for i in range(n):
        ch=bit%2
        bit//=2
        if ch==1:
            for k in range(m+1):
                al[k]+=book[i][k]
    if min(al[1:])>=x:
        ans=min(ans,al[0])

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

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

books = []

for _ in range(n):
    cost, *power = map(int, input().split())
    books.append((cost, power))


def check(levels, limit):
    for level in levels:
        if level >= limit:
            continue
        else:
            return False

    return True


candidates = []
for pattern in range(2 ** n):
    levels = [0] * m
    result = 0
    for num in range(n):
        if (pattern >> num) & 1:
            cost, powers = books[num]
            result += cost
            for idx in range(m):
                levels[idx] += powers[idx]

    if check(levels, x):
        candidates.append(result)

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

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

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

import itertools

D = list(itertools.product([0, 1], repeat=n))
E = [0] * m
total = 0
ans = 0
F = []
for i in D:
    ans = 0
    E = [0] * m
    total = 0
    for j in range(len(i)):
        if i[j] == 1:
            for k in range(len(B[j])):
                E[k] += B[j][k]
            total += A[j]
    for l in E:
        if l >= x:
            continue
        else:
            ans = 1
            break
    if ans == 0:
        F.append(total)
if F == []:
    print(-1)
else:
    print(min(F))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


import itertools

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

best = None
for use in itertools.product(*[[True, False] for _ in range(n)]):
    vals = [0] * m
    nedan = sum([v for i,v in enumerate(c) if use[i]])
    for i,u in enumerate(use):
        if u:
            for j,v in enumerate(a[i]):
                vals[j] += v
    if all([item>=x for item in vals]):
        best = min(best, nedan) if best is not None else nedan
if best is not None:
    print(best)
else:
    print(-1)

Solution (Python):
N, M, X = [int(x) for x in input().split()]
costs = []
A = []
for i in range(N):
    line = [int(x) for x in input().split()]
    costs.append(line[0])
    A.append(line[1:])

best = float('inf')
for mask in range(2 ** N):
    totalCost = 0
    skills = [0] * M
    for i in range(N):
        if (1 << i) & mask:
            totalCost += costs[i]
            for j in range(M):
                skills[j] += A[i][j]
    if all(x >= X for x in skills):
        best = min(best, totalCost)

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

Solution (Python):
import itertools
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for _ in range(N)]
ll=list(itertools.product(range(2),repeat=N))
ans=10**10
for l in ll:
    t=0
    a=[0]*M
    for i in range(N):
        if l[i]==1:
            t+=CA[i][0]
            for j in range(M):
                a[j]+=CA[i][j+1]
    for i in range(M):
        if a[i]<X:
            break
    else:
        ans=min(ans,t)
if ans==10**10:
    print(-1)
else:
    print(ans)

Solution (Python):
N,M,X= map(int,input().split())
C = []
A = []
for i in range(N):
    I = list(map(int,input().split()))
    C.append(I[0])
    A.append(I[1:])
min = 10 ** 9
for i in range(2**N):
    U = [0 for i in range(M)]
    c = 0
    I = bin(i)[2:]
    I = "0"*(N-len(I)) + I
    for j in range(N):
        if int(I[j]):
            c += C[j]
            a = A[j]
            for s in range(M):
                U[s] = U[s] + a[s]
    state = 1
    for s in range(M):
        if U[s] < X:
            state = 0
            break
    if state:
        if min >= c:
            min = c
if min ==10 ** 9:
    print(-1)
else:
    print(min)

Solution (Python):
import numpy as np

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

Cs = []
As = []
for _ in range(N):
    t = tuple(map(int, input().split()))
    Cs.append(t[0])
    As.append( np.array(t[1:]) )

mincost = 10 ** 10
for i in range(2 ** N):
    cost = 0
    skills = np.zeros(M, np.int64)
    for j in range(N):
        if i & (1 << j):
            skills += As[j]
            cost += Cs[j]
    if np.amin(skills) >= X:
        mincost = min(mincost, cost)

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

Solution (Python):
from itertools import combinations
from collections import deque

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

c = []
a = []
for _ in range(n):
	tmp = deque(map(int,input().split()))
	c.append(tmp.popleft())
	a.append(list(tmp))

l = []
ans = 10 ** 9
for i in range(2**n):
	l = []
	tmp = 0
	for j in range(n):
			if i & (1<<j):
				l.append(j)
				tmp += c[j]
	res = [0 for _ in range(m)]
	for j in l:
		for k in range(m):
			res[k] += a[j][k]
	flag = True
	for j in range(m):
		if res[j] < x:
			flag = False
			break
	if flag:
		ans = min(ans,tmp)

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

Solution (Python):
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(n)]
true_buy = float("inf")
for i in range(2**n):
  buy = []
  buy_sum = 0
  for j in range(n):
    if (i>>j) & 1:
      buy.append(ca[j])
      buy_sum += ca[j][0]
  for k in range(m):
    gain = 0
    for l in range(len(buy)):
      gain += buy[l][k+1]
    if gain < x:
      buy_sum = float("inf")
  true_buy = min(buy_sum,true_buy)
if true_buy == float("inf"):
  print(-1)
else:
  print(true_buy)

Solution (Python):
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
INF=float("inf")
ans=INF
for i in range(2**n):
    tl=[0]*m
    c=0
    for j in range(n):
        if (i>>j)&1:
            c+=l[j][0]
            for k,a in enumerate(l[j][1:]):
                tl[k]+=a
    for j in tl:
        if j<x:
            break
    else:
        ans=min(ans,c)
if ans==INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n,m,x = map(int, input().split())
cas = [tuple(map(int,input().split())) for i in range(n)]

ans = float('inf')


for i in range(2 ** n):
    d = [0]*m
    tmp = 0
    for j in range(n):  
        if ((i >> j) & 1):  
            ca = cas[j]
            c= ca[0]
            for k,a in enumerate(ca[1:]):
                d[k]+=a
            tmp+=c

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

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

Solution (Python):
def main():
    N, M, X = list(map(int, input().split()))
    C = []
    A = []
    for _ in range(N):
        c, *a = list(map(int, input().split()))
        C.append(c)
        A.append(a)
    INF = 10 ** 9
    r = INF
    for pat in range(2 ** N):
        m = [sum(A[i][j] for i in range(N) if pat & (1 << i)) for j in range(M)]
        if not all(i >= X for i in m):
            continue
        c = sum(C[i] for i in range(N) if pat & (1 << i))
        r = min(r, c)
    return -1 if r == INF else r

print(main())

Solution (Python):

import os
import sys
from io import BytesIO, IOBase





def main():
    n,m,xk=[int(x) for x in input().split()]
    books=[ [int(x) for x in input().split()] for _ in range(n)]
    ans=10**8

    for msk in range(2**n):
        cst=0
        bk=[0]*m
        for i in range(n):
            if not msk&1<<i:
                continue
            cst+=books[i][0]
            for i,x in enumerate(books[i][1:]):
                bk[i]+=x
        
        for k in bk:
            if k<xk:
                break
        else:
            
            ans=min(ans,cst)

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



BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
N,M,X=map(int,input().split())
s=[list(map(int,input().split())) for i in range(N)]
a=10**12
from itertools import product
for i in product([0,1], repeat=N):
    c=0
    for j in range(N):
        if i[j]:
            c+=s[j][0]
    if c>a:
        continue
    for j in range(M):
        t=0
        for k in range(N):
            if i[k]:
                t+=s[k][j+1]
        if t<X:
            break
    else:
        if c<a:
            a=c
print(a if a!=10**12 else -1)

Solution (Python):

N, M, X = map(int, input().split())
L = []
ans = float("inf")
flag = False
for i in range(N):
    L.append(list(map(int, input().split())))
    
for i in range(2**N):
    bit = i
    use = []
    skill = [0 for _ in range(M)]
    money = 0
    for j in range(N):
        if (bit >> j & 1) == 1:
            money += L[j][0]
            for k in range(1, M+1):
                skill[k-1] += L[j][k]
    tmp = True
    for k in range(M):
        if skill[k] < X:
            tmp = False
    if tmp:
        flag = True
        ans = min(ans, money)
if flag:
    print(ans)
else:
    print(-1)

Solution (Python):
N, M, X = map(int,input().split())
books = []
for _ in range(N):
    books.append(list(map(int,input().split())))
ans = float('inf')
for i in range(2 ** N):
    money = 0
    algo = [0 for _ in range(M)]
    for j in range(N):
        if i & 1 == 1:
            money += books[j][0]
            for k in range(M):
                algo[k] += books[j][k+1]
        i >>= 1
    if all([j >= X for j in algo]):
        ans = min(ans, money)

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

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

    info = [tuple(map(int, input().split())) for _ in range(N)]
    INF = 10 ** 18
    ans = INF

    for bit in range(1<<N):
        cost = 0
        x = [0] * M
        for i in range(N):
            if (bit>>i) & 1:
                cost += info[i][0]
                for j in range(M):
                    x[j] += info[i][j+1]
        
        
        if all([True if X <= y else False for y in x]):
            ans = min(ans, cost)
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

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

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

import numpy as np

def solve():
    n, m, x = MI()
    C = [0] * n
    A = [None] * n
    for i in range(n):
        tmp = LI()
        c = tmp[0]
        a = tmp[1:]
        C[i] = c
        A[i] = a
    
    

    ans = INF
    for i in range(pow(2, n)):
        bag = []
        for j in range(n):
            if 1 & (i >> j):
                bag.append(j)

        a = np.array([0] * m)
        c = 0
        for b in bag:
            a += np.array(A[b])
            c += C[b]

        
        if all(a >= x):
            ans = min(ans, c)

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



if __name__ == '__main__':
    solve()

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

ans=float("inf")

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

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

calist=[]
for i in range(N):
  c,*alist=list(map(int,input().split()))
  calist.append((c,alist))


answer=float("inf")
for perm in itertools.product(range(2),repeat=N):
  
  if sum(perm)==0:
    continue
    
  perm_price=0
  achieve=[0]*M
  for i in range(N):
    if perm[i]==0:
      continue
    
    ci,alist=calist[i]
    perm_price+=ci
    for j in range(M):
      achieve[j]+=alist[j]
      
  if min(achieve)>=X:
    answer=min(answer,perm_price)
    
if answer==float("inf"):
  print(-1)
else:
  print(answer)

Solution (Python):
n,m,x=map(int,input().split())
lis=[tuple(map(int,input().split()))for _ in range(n)]
ans = 2**60
for i in range(2**n):
    tmp = []
    vals=[0]*m
    for j in range(n):
        if i>>j&1:
            tmp.append(lis[j])
    cost=0
    flag=0
    for t in tmp:
        cost += t[0]
        for k in range(m):
            vals[k]+=t[k+1]
    for k in range(m):
        if vals[k]<x:
            flag=1
            break
    if flag:continue
    else:
        ans = min(ans,cost)
if ans == 2**60:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



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


ans = INF
for i in range(1 << n):
    bit = bin(i)[2:].zfill(n)
    
    z = [0 for _ in range(m)]
    price = 0
    for j in range(n):
        if bit[j] == "1":
            price += c[j]
            for k in range(m):
                z[k] += a[j][k]
    ok = True
    for j in z:
        if j < x:
            ok = False
            break
    if ok:
        ans = min(ans, price)
if ans == INF:
    print(-1)
else:
    print(ans)

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

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

ans=10**9
for i in range(2**n):
    status=[False]*n
    for j in range(n):
        if ((i>>j)&1):
            status[j]=True
            
    score=[0]*m
    total=0
    
    for k in range(n):
        if status[k]==True:
            for x in range(m+1):
                if x==0:
                    total+=a[k][0]
                else:
                    score[x-1]+=a[k][x]

    flag=True
    for i in score:
        if i<target:
            flag=False
    
    if flag:
        ans=min(ans,total)
if ans ==10**9:
    ans=-1
print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, X = MAP()
C = [0] * N
A = [[]] * N
for i in range(N):
    C[i], *A[i] = MAP()

ans = INF
for bit in range(1<<N):
    skills = [0] * M
    cost = 0
    for i in range(N):
        if bit>>i & 1:
            cost += C[i]
            for j in range(M):
                skills[j] += A[i][j]
    if min(skills) >= X:
        ans = min(ans, cost)
if ans == INF:
    print(-1)
else:
    print(ans)

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


ans = 10 ** 7
flag = False
for i in range(1, 2 ** N):
    cost = 0
    under = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            for k in range(M):
                under[k] += A[j][k]
    if all([val >= X for val in under]):
        ans  = min(ans, cost)
        flag = True
if flag:
    print(ans)
else:
    print(-1)

Solution (Python):
import itertools

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

MAX = 10 ** 7
ans = MAX
for t in itertools.product((0, 1), repeat=N):
    A = [sum(t[j] * B[j][i + 1] for j in range(N)) for i in range(M)]
    if all(a >= X for a in A):
        ans = min(ans, sum(t[j] * B[j][0] for j in range(N)))
print(ans if ans != MAX else -1)

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    

    def dump(*args):
        sys.stderr.write(str(args))

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

    def dfs(i, su):
        if i == n:
            for al in rikaido:
                if al < x:
                    return 10 ** 12
            return su
        for j in range(m):
            rikaido[j] += a[i][j+1]
        t = dfs(i + 1, su + a[i][0])
        for j in range(m):
            rikaido[j] -= a[i][j+1]
        return min(t, dfs(i+1, su))

    ans = dfs(0, 0)

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


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, X = map(int, input().split())
c = []
A = [[] for _ in range(N)]
for j in range(N):
	tmp = list(map(int, input().split()))
	for i in range(M+1):
		if i == 0:
			c.append(tmp[i])
		else:
			A[j].append(tmp[i])
A = np.array(A)
ans = 10**10
cond = 0
for s in range(1 << N):
	flg = np.zeros(M)
	cost = 0
	for i in range(N):
		if (s >> i) & 1 == 1:
			flg += A[i]
			cost += c[i]
	if np.count_nonzero(flg < X) == 0:
		cond = 1
		ans = min(ans, cost)
if cond:
	print(ans)
else:
	print(-1)

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

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


def main():
    N, M, X = map(int, input().split())
    C = [0] * N
    A = [0] * N
    for i in range(N):
        c, *a = map(int, input().split())
        C[i] = c
        A[i] = a

    min_price = INF
    for r in range(1, N + 1):
        for comb in combinations(range(N), r):
            skills = [0] * M
            for i in range(N):
                if i in comb:
                    for j in range(M):
                        skills[j] += A[i][j]

            if all(s >= X for s in skills):
                total_price = sum(c for i, c in enumerate(C) if i in comb)
                if min_price > total_price:
                    min_price = total_price

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

    return


if __name__ == '__main__':
    main()