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())
C_A = [list(map(int, input().split())) for i in range(N)]

ans = float('inf')
def dfs(i, now, cost):
    global ans
    if i == N:
        if all(elem >= X for elem in now):
            ans = min(cost, ans)
    else:
        dfs(i+1, now, cost)
        A = C_A[i][1:]
        now_next = [x + y for (x, y) in zip(now, A)]
        dfs(i+1, now_next, cost+C_A[i][0])

dfs(0, [0]*M, 0)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):

"""
Created on Sun May 10 20:54:30 2020

@author: Kanaru Sato
"""

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

mincost = 10**9

for state in range(2**n):
    rikaido = [0 for i in range(m)]
    rikaishita = 1
    cost = 0
    for k in range(n):
        if (state&(1<<k))>>k:
            cost += costs[k]
            for i in range(m):
                rikaido[i] += a[k][i]
    for i in range(m):
        if rikaido[i] < x:
            rikaishita = 0
    if rikaishita == 1:
        mincost = min(mincost,cost)

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

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

book = []

for i in range(N):
    tmp = list(map(int, input().split()))
    book.append(tmp)

def check(ans):
    for i in range(len(ans)):
        if ans[i] < X:
            return 0
    return 1

price_sum = float("inf")
for i in range(2 ** N):
    ans = [0] * M
    tmp = 0
    for j in range(N):
        if (i >> j & 1):
            tmp += book[j][0]
            for k in range(1, M+1):
                ans[k-1] += book[j][k]
    if check(ans):
        price_sum = min(price_sum, tmp)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M,X = mis()
    B = [lmis() for _ in range(N)]
    ans = INF
    for b in range(2**N):
        pt = [0]*(M+1)
        for i in range(N):
            if (1<<i)&b:
                for j in range(M+1):
                    pt[j] += B[i][j]
        if min(pt[1:])>=X:
            ans = min(ans, pt[0])
    print(ans if ans!=INF else -1)




main()

Solution (Python):



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

books = []
able = [0 for _ in range(m)]

for i in range(n):
    book = list(map(int, input().split()))
    books.append(book)
    for idx, j in enumerate(book[1:]):
        able[idx - 1] += j

if min(able) < x:
    print(-1)
    exit()

ans = float('INF')
for flags in list(itertools.product(range(2), repeat=n)):
    able = [0 for _ in range(m)]
    cost = 0
    for bo, flag in enumerate(flags):
        if flag:
            book = books[bo]
            for idx, j in enumerate(book):
                if idx == 0:
                    cost += j
                else:
                    able[idx - 1] += j

    if min(able) >= x:
        ans = min(cost, ans)

print(ans)

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


def solve(i, j, item):
    if i == N:
        for k in item:
            if k < X:
                return float("inf")
        return j

    return min([solve(i + 1, j + item_list[i][0], item + item_list[i][1:]), solve(i + 1, j, item)])


ans = solve(0, 0, [0 for i in range(M)])
if ans != float("inf"):
    print(ans)
else:
    print(-1)

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

ans = 1000000000
for i in range(1 << n):
     score = [0 for _ in range(m)]
     tmp = i
     t = 0
     for j in range(n):
         if tmp & 1:
             for k in range(m):
                 score[k] += ca[j][k + 1]
             t += ca[j][0]
         tmp >>= 1
     if x <= min(score):
         ans = min(ans, t)
if ans == 1000000000:
    ans = -1
print(ans)

Solution (Python):
n, m, x = map(int, input().split())
G = []
ans = float('inf')
for _ in range(n):
    G.append(list(map(int, input().split())))
for i in range(1<<n):
    dummy = 0
    l = [0]*m
    flag = True
    for j in range(n):
        if (i>>j)&1 == 1:
            for k in range(m):
                l[k] += G[j][k+1]
            dummy += G[j][0]
    for p in range(m):
        if l[p] < x:
            flag = False
            break
    if flag == True:
        ans = min(ans, dummy)

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

Solution (Python):
n,m,x=map(int,input().split())
info=[]
for i in range(n):
    z=list(map(int,input().split()))
    info.append(z)
ans=10**9
for i in range(2**n):
    skill=[x]*m
    total=0
    for j in range(n):
        if (i>>j)&1: 
            total+=info[j][0]
            for k in range(m):
                skill[k]-=info[j][1+k]
            flag=True
            for k in range(m):
                if 0<skill[k]:
                    flag=False
                    break
            if flag:
                if total<ans:
                    ans=total
print(ans if ans<10**9 else -1)

Solution (Python):
from collections import defaultdict as dd
from itertools import product

N,M,X=map(int,input().split())
a = [list(map(int,input().split())) for _ in range(N)]
res = 10**18
gen = [0,1]
for ls in product(gen,repeat=N):
    tmp = 0
    tmp2 = [0]*M
    for i in range(N):
        if ls[i] == 1:
            tmp += a[i][0]
            for j in range(M):
                tmp2[j] += a[i][j+1]
    for j in range(M):
        if tmp2[j] < X:
            tmp = 10**18
            break
    if tmp < res:
        res = tmp

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

Solution (Python):
import numpy as np
import sys
import math

N , M , X = map(int,input().split())
data = []
[data.append(list(map(int,input().split()))) for _ in range(N)]
ten = 1000000 * 12
ans = 1000000 * 12
for x in range(2**N):
    bi = bin(x)[2::][::-1]
    tmp = [0] * M
    cost = 0
    for index , b in enumerate(bi) :
        if b == "1":
            cost += data[index][0]
            for i , d in enumerate(data[index][1::]):
                tmp[i] += d
    flag = 0
    for tt in tmp :
        if tt < X:
            flag = 1
            break
    if flag == 0:
        ans = min(cost , ans)

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

Solution (Python):
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
ans=100000000000000000
for i in range(2**n):
    check=[0]*m
    ans_=0
    for j in range(n):
        if ((i>>j)&1):
            ans_+=ca[j][0]
            for k in range(m):
                check[k]+=ca[j][k+1]
    
    if all([l>=x for l in check]):
        
        ans=min(ans,ans_)
if ans==100000000000000000:
    print(-1)
else:
    print(ans)

Solution (Python):
from itertools import combinations

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

res = float('inf')
for r in range(N + 1):
    for c in combinations(range(N), r):
        skills = [0] * M
        price = 0
        for i in c:
            price += books[i][0]
            for j, a in enumerate(books[i][1:]):
                skills[j] += a
        if all(skill >= X for skill in skills):
            res = min(res, price)

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

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]

def to_bin(x: int) -> str: return format(x, 'b') 
def to_oct(x: int) -> str: return format(x, 'o') 
def to_hex(x: int) -> str: return format(x, 'x') 
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res

from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left


def main():
    n, m, x = MII()
    query = [MII() for _ in range(n)]
    mincost = 10**7
    for bit in range(1<<n):
        vals = [0]*m
        cost = 0
        for i in range(n):
            if bit&(1<<i):
                cost += query[i][0]
                for i, c in enumerate(query[i][1:]):
                    vals[i] += c
                x_g = [1 for v in vals if v >= x]
                if sum(x_g) == m:
                    mincost = min(cost, mincost)
    if mincost == 10**7:
        print(-1)
    else:
        print(mincost)

if __name__ == '__main__':
    main()

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)

queue = [(0,[0 for _ in range(m)],0)]
ans = float('inf')
while queue:
  cost, learn, index = queue.pop(-1)
  if all([l>= x for l in learn]):
    ans = min(ans, cost)
    continue
  if index == n:
    continue
  else:
    queue.append((cost, learn, index+1))
    queue.append((cost+C[index], [learn[i]+A[index][i] for i in range(m)], index+1))
    
print(ans if ans != float('inf') else -1)

Solution (Python):
import itertools

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

ans = float("inf")
for x in list(itertools.product([0,1], repeat=N)):
    tmp = 0
    tmp_A = [0] * M
    for i in range(N):
        if x[i] == 1:
            tmp += CA[i][0]
            for j in range(M):
                tmp_A[j] += CA[i][1+j]
    if min(tmp_A) >= X:
        ans = min(ans, tmp)

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

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M, X = lr()
CA = np.array([lr() for _ in range(N)])
INF = 10 ** 9
answer = INF
for pattern in range(1<<N):
    temp = 0
    algo = np.zeros(M+1, dtype=np.int32)
    for i in range(N):
        if (pattern>>i) & 1:
            algo += CA[i]
    if np.all(algo[1:] >= X) and algo[0] < answer:
        answer = algo[0]

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

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

maxa = [0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxa[j] += ca[i][j+1]
ans = 10**7
for i in range(m):
    if maxa[i] < x:
        ans = -1
        break



def sankousyo(l):
    if len(l) == n:
    
        global ans
        kingaku = 0
        maxa_k = [0 for i in range(m)]
        for i in range(n):
            if l[i] == 1:
                for j in range(m):
                    maxa_k[j] += ca[i][j+1]
        for i in range(m):
            if maxa_k[i] < x:
                kingaku = -1
                break
        if kingaku != -1:
            for i in range(n):
                if l[i] == 1:
                    kingaku += ca[i][0]
            ans = min(ans,kingaku)
    else:
        sankousyo(l+[0])
        sankousyo(l+[1])
    
if ans == 10**7:
    sankousyo([])

print(ans)

Solution (Python):
n , m , x = map(int,input().split())
san = []
for i in range(n):
    san.append(list(map(int,input().split())))
ans = 10**8
for b in range(2**n):
    bs = format(b, 'b')
    bs = str(bs).rjust(n,'0')
    one = 0
    p = [0 for i in range(m)]
    for i in range(n):
        if bs[i] == "1":
            one += san[i][0]
            for j in range(1,m+1):
                p[j-1] += san[i][j]
    if min(p) >= x:
        ans = min(ans,one)
if ans == 10**8:
    print(-1)
else:
    print(ans)

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

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


ans=10**9
for i in range(2**N):
    I=i
    cost=0
    LIST=[]
    for j in range(N):
        if I//(2**(N-1-j))==1:
            LIST.append(L[j])
        I%=(2**(N-1-j))
    
    for j in range(len(LIST)):
        cost+=LIST[j][0]
    if cost<ans:
        Sum=[0 for i in range(M)]
        for j in range(len(LIST)):
            for k in range(M):
                Sum[k]+=LIST[j][k+1]
        
        if min(Sum)>=X:
            ans=cost
if ans==10**9:
    print(-1)
else:
    print(ans)

Solution (Python):
N,M,X=map(int,input().split())
lst=[[0 for e in range(M+1)] for f in range(N)]
for i in range(N):
 lst[i]=list(map(int,input().split()))
F=10**7
for i in range(2**N):
 E=0
 Sui=[0]*N
 for j in range(N):
  if ((i >> j) & 1):
   Sui[j]+=1
 skl=[0]*M
 cost=0
 for k in range(N):
  if Sui[k]==1:
   for t in range(M):
    skl[t]+=lst[k][t+1]
   cost+=lst[k][0]
 E=0
 for t in range(M):
  if skl[t]>=X:
   E+=1
 if E==M:
  F=min(cost,F)
if F==10**7:
 print(-1)
else:
 print(F)

Solution (Python):
import math
import sys
sys.setrecursionlimit(10**9)

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

    INF = 10**20
    ans = INF
    for i in range(2**N):
        cost = 0
        algs = [0]*M
        for j in range(N):
            if (i >> j) & 1:
                cost += book[j][0]
                for k in range(M):
                    algs[k] += book[j][k+1]

        ng = False
        for alg in algs:
            if alg < X:
                ng = True

        if not ng:
            ans = min(ans,cost)

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


if __name__ == "__main__":
  main()

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

def calc(state):
    ret = 0
    S = [0] * M
    for i, B in enumerate(A):
        if ((1 << i) & state) == 0:
            continue
        for j, a in enumerate(B[1:]):
            S[j] += a
        ret += B[0]
    if all(s >= X for s in S):
        return ret
    return 10**18

ans = 10**18
for state in range(1 << N):
    ans = min(ans, calc(state))

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

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

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

ans=10**15

for comb in bit:
    pri=0
    R=[0 for i in range(m)]
    for i in range(n):
        if comb[i]==1:
            pri+=C[i][0]
            for q in range(m):
                R[q]+=C[i][q+1]
    if min(R)>=x:
        ans=min(ans,pri)

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

Solution (Python):
import numpy as np

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

C = [0]*N
A = np.array([[0]*M for i in range(N)])

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

min_ans = 10**10
flg = False
for i in range(2**N):
    tmp_A = np.array([0] * M)
    tmp_C = 0
    for j in range(N):
        if ((i >> j) & 1):
            tmp_A += A[j]
            tmp_C += C[j]
    if (tmp_A >= X).sum() == M and tmp_C < min_ans:
        min_ans = tmp_C
        flg = True

if flg:
    print(min_ans)
else:
    print("-1")

Solution (Python):
INF = 10**18

N, M, X = map(int, input().split())
C = [0]*N
A = [[] for i in range(N)]
for i in range(N):
    src = list(map(int, input().split()))
    C[i] = src[0]
    A[i] = src[1:]
ans = INF
for i in range(1<<N):
    point = [0]*M
    m = 0
    for j in range(N):
        if i&(1<<j) > 0:
            m += C[j]
            for ii, a in enumerate(A[j]):
                point[ii] += a
    ok = True
    for j in range(M):
        if point[j] < X:
            ok = False
            break
    if ok:
        ans = min(ans, m)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):




import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m,x=map(int, readline().rstrip().split())
    memo=[[0 for i in range(m+1)] for j in range(n)]
    for i in range(n):
        memo[i]=list(map(int, readline().rstrip().split()))

    loops=[[0,1] for i in range(n)]

    minCost=9999999999
    for loop2 in list(itertools.product(*loops)):
        cost=0
        loop=list(loop2)
        algo=[0]*m
        for l in range(len(loop)):
            if loop[l]==1:
                cost+=memo[l][0]
                for a in range(m):
                    algo[a]+=memo[l][a+1]
        if min(algo) >=x:
            minCost=min(minCost,cost)
    if minCost==9999999999:
        print(-1)
    else:
        print(minCost)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Solution (Python):
import sys
import numpy as np
from itertools import product 
input = sys.stdin.readline
N,M,X= map(int,input().split())
CA = [list(map(int,input().split())) for i in range(N)]
C,*A = zip(*CA)
C = np.array(C)
A = np.array(A)

inf = 10**8
ans = inf

l = [1,0]
for c in product(l,repeat=N):
    Y = c * A
    Y = np.sum(Y,axis=1)
    if np.all((Y-X) >= 0):
        ans = min(ans, np.sum(c*C))

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

Solution (Python):
from itertools import product
n,m,k = map(int,input().split())
l = list(list(map(int,input().split())) for i in range(n))

a = [0,1]
mi = 10**8
for i in product(a,repeat=n):
  money = 0
  tishiki = list(0 for i in range(m))
  for j in range(n):
    q = i[j]
    if q==1:
      money += l[j][0]
      for e in range(m):
        tishiki[e] += l[j][e+1]
  for v in tishiki:
    if v<k:
      break
  else:
    mi = min(mi,money)
if mi==10**8:
  print(-1)
else:
  print(mi)

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve(idx, cur, cost):
    
    if(idx==n):
        
        flag = 0
        for el in cur:
            if(el<x):
                flag = 1
                break
        if(flag==0):
            return cost
        else:
            return INF

    cur1 = [0]*m
    for i, el in enumerate(a[idx]):
        cur1[i] += el+cur[i]
    temp1 = solve(idx+1, cur1, cost+c[idx])
    temp2 = solve(idx+1, cur, cost)

    return min(temp1, temp2)

n,m,x = MAP()

c = []
a = []

for _ in range(n):
    temp = LIST()
    c.append(temp[0])
    a.append(temp[1:])

curr = [0]*m
ans = solve(0, curr, 0)
if(ans==INF):
    print(-1)
else:
    print(ans)

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

ans = 10**9

for i in range(2 ** N):
    money = 0
    L = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            money += book[j][0]
            for m in range(M):
                L[m] += book[j][m+1]
    
    for m in range(M):
        if L[m] < X:
            break
    else:
        ans = min(ans, money)

if ans == 10**9:
    ans = -1

print(ans)

Solution (Python):
import itertools
N, M, X = map(int, input().split())
a = [list(map(int,input().split())) for i in range (N)]
nums = [0,1]
c = float('inf')
for balls in itertools.product(nums, repeat=N):
  g = 1
  for j in range(M):
    if X>sum([balls[i]*a[i][j+1] for i in range(N)]):
      g = 0
  if g == 1:
    c = min(c, sum([balls[i]*a[i][0] for i in range(N)]))
if c != float('inf'):
  print(c)
else:
  print(-1)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,X = LI()

    c = []
    s = []
    for _ in range(N):
        x = LI()
        c.append(x[0])
        s.append(x[1:])


    ans = INF
    for i in range(1,2**N):
        t = [0] * M
        b = 1
        cost = 0
        for j in range(N):
            if i & b:
                for k in range(M):
                    t[k] += s[j][k]
                cost += c[j]
            b <<= 1
        for x in t:
            if x < X: break
        else:

            ans = min(ans,cost)
    if ans < INF:
        print(ans)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

ans = 100000000000
for k in range(1, n + 1):
    for cmb in itertools.combinations(range(n), k):
        d = [0] * m
        cost = 0
        for cm in cmb:
            cost += c[cm]
            for i in range(m):
                d[i] += a[cm][i]

        f = True
        for i in range(m):
            if d[i] < x:
                f = False
                break
        if f:
            ans = min(ans, cost)

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

Solution (Python):
n,m,x=map(int,input().split())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))
min=13*100000

for i in range(2**n):
    s=0
    m1=[0 for i in range(m)]
    for j in range(n):
        if (i>>j&1):
            s+=a[j][0]
            for k in range(m):
                m1[k]+=a[j][k+1]
    for j in range(m):
        if m1[j]<x:
            break
    else:
        if s<min:
            min=s
if min!=13*100000:
    print(min)
else:
    print(-1)

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

anm = [None] * n
cn = [None] * n
for i in range(n):
    row = list(map(int, input().split(' ')))
    cn[i] = row[0]
    anm[i] = row[1:]

ans = float('inf')
for i in range(2 ** n):
    cost = 0
    ex = [0] * m
    for j in range(n):
        if i >> j & 1:
            cost += cn[j]
            for k in range(m):
                ex[k] += anm[j][k]
    if sum(1 for e in ex if e >= x) == m and ans > cost:
        ans = cost

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

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    
    
    
    import numpy as np
    
    
    input = stdin.readline


    n, m, x = map(int, input().split())
    cc = [0]*n
    aa = [0]*n
    for i in range(n):
        c, *a = map(int, input().split())
        cc[i] = c
        aa[i] = np.array(a)
    ans = sum(cc)+1
    for i in range(2**n):
        understand = np.array([0]*m)
        total = 0
        for j in range(n):
            if ((i >> j) & 1):
                understand += aa[j]
                total += cc[j]
        if (understand>=x).all() and ans > total:
            ans = total
    if ans == sum(cc)+1:
        print('-1')
    else:
        print(ans)

Solution (Python):
N,M,K= list(map(int, input().split()))
C = []
A = []
for _ in range(N):
    c= list(map(int, input().split()))
    C.append(c[0])
    A.append(c[1:])
inf = float('inf')
ans = inf

for i in range(2**N):
    re = [0]*M
    count = 0
    for j in range(N):
        if((i>>j)&1):
            count += C[j]
            for k in range(M):
                re[k] += A[j][k]
    
    flag = True
    for n in range(M):
        if re[n] < K:
            flag = False
    
    if flag:
        ans = min(ans,count)

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

Solution (Python):
from itertools import product
import numpy as np
N,M,X=map(int,input().split(' '))
Books=[np.array(list(map(int,input().split(' ')))) for i in range(N)]
A=[0]*M
maxi = sum([Books[i][0] for i in range(N)])+1
ans = maxi
for i in product([0,1],repeat=N):
    tmp = np.array([0]*M)
    t_ans = 0
    for n,j in enumerate(i):
        if j:
            tmp += Books[n][1:]
            t_ans += Books[n][0]
    if tmp.min() >=X:
        ans = min(ans,t_ans)
if ans < maxi:
    print(ans)
else:
    print(-1)

Solution (Python):
n, m, x = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')
for i in range(2**(n)):
    table = [0]*m
    money = 0
    for j in range(n):
        if ((i >> j) & 1):
            money += lis[j][0]
            for k in range(m):
                table[k] += lis[j][k+1]
    if all([table[i] >= x for i in range(m)]):
        ans = min(ans, money)
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Solution (Python):
from itertools import chain, combinations

def powerset(iterable):
    """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
    """
    xs = list(iterable)
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))


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

subsets = list(powerset([i for i in range(N)]))
ans = float('inf')
for item in subsets:
    if not item:
        continue
    tmp = [0] * (M + 1)
    cost = 0
    for idx in item:
        cost += arr[idx][0]
        for i, v in enumerate(arr[idx]):
            tmp[i] += v
    flag = True
    for i in range(1, M+1):
        if X > tmp[i]:
            flag = False
    if flag:
        ans = min(ans, cost)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
from collections import deque

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=[]
    for j in range(1,M+1):
        a.append(l[j])
    A.append(a)
ans=10**10
flag=False
for i in range(2**N):
    op=["-"]*N
    for j in range(N):
        if ((i>>j)&1):
            op[N-1-j]="+"
    tmp=0
    l=[0]*M
    for j in range(N):
        if op[j]=="+":
            tmp+=C[j]
            for k in range(M):
                l[k]+=A[j][k]
    f=True
    for j in range(M):
        if l[j]<X:
            f=False
    if f:
        flag=True
        ans=min(ans,tmp)

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

Solution (Python):


import numpy as np


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

ans = 10**10
for bit in range(2**N):
    tc = 0
    ta = np.zeros(M)
    for i in range(N):
        if bit & (1 << i):
            tc += C[i]
            ta += np.array(A[i])
    if min(ta) >= X:
        ans = min(tc, ans)
if ans == 10**10:
    print(-1)
else:
    print(ans)