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):






"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple

MAX = 13 * pow(10, 5)


def solve(
    prices: List[int], values: List[List[int]], target: int, rows: int, cols: int
) -> Optional[int]:
    min_price = MAX
    for i in range(rows):
        for picked in itertools.combinations(range(rows), i + 1):
            for j in range(cols):
                if sum(values[k][j] for k in picked) < target:
                    break
            
            else:
                min_price = min(min_price, sum(prices[k] for k in picked))
    return min_price if min_price < MAX else None
    
    dp = [[(0, 0)] * cols for _ in rows]
    for i in range(rows):
        pi = prices[i]
        vi = values[i]
        dp = []
        for j in range(cols):
            if l < target:
                dp.append((pi + p, l + vi[j]))
    return target


def do_job():
    "Do the work"
    LOG.debug("Start working")
    
    N, M, X = map(int, input().split())
    values = []
    prices = []
    for _ in range(N):
        p, *v = map(int, input().split())
        assert len(v) == M
        prices.append(p)
        values.append(v)
    result = solve(prices, values, X, N, M)
    print(result if result else -1)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 
    
    


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None

if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            
            
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Solution (Python):
import sys
input = sys.stdin.readline
n,m,x = map(int,input().split())
c = []
a = []
ans = 10**9
check = False
for _ in range(n):
  dc,*da = map(int,input().split())
  c.append(dc)
  a.append(da)
for i in range(1,1<<n):
  study = [0]*m
  total = 0
  for j in range(n):
    if (i>>j)%2:
      total += c[j]
      for k in range(m):
        study[k] += a[j][k]
  if all([l>=x for l in study]):
    check = True
    ans = min(ans,total)
if check:
  print(ans)
else:
  print(-1)

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

ans = []
for i in range(2**n):
  pat = [0] * n
  r = [0] * m
  money = 0
  for j in range(n):
    if ((i>>j)&1):
      pat[n-1-j] = 1
  for x in range(len(pat)):
    if pat[x] == 1:
      money += a[x][0]
      for y in range(m):
        r[y] += a[x][y+1]
  flag = True
  for z in range(m):
    if r[z] < X: 
      flag = False
      break
  if flag: 
    ans.append(money)
print(min(ans) if ans else -1)

Solution (Python):
def main():
    n ,m, x = map(int, input().split())
    c, a = [0 for i in range(n)], [[0 for i in range(m)] for j in range(n)]
    for i in range(n):
        c[i], *a[i] = [int(i) for i in input().split()]
    ans = solve(n, m, x, c, a)
    print(ans)


def solve(n, m, x, c, a):
    INF = 10 ** 9
    ans = INF
    for bits in range(2 ** n):
        cost, skill = 0, [0 for i in range(m)]
        
        for i in range(n):
            bit = bits >> i & 1
            
            if bit:
                cost += c[i]
                for j in range(m):
                    skill[j] += a[i][j]
        
        if judge(skill, x):
            ans = min(ans, cost)
    return -1 if ans == INF else ans

def judge(skill, x):
    for i in skill:
        if i < x:
            return False
    return True

if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import numpy as np
n, m, x = map(int, input().split())
temp = [list(map(int, input().split())) for _ in range(n)]
ans = []
for li in itertools.product([0,1], repeat=n):
    cnt = 0
    check = np.zeros(m, np.int)
    for i in range(n):
        if li[i] == 1:
            check += np.array(temp[i][1:])
            cnt += temp[i][0]
    if min(check) >= x:
        ans.append(cnt)
print(min(ans) if len(ans) !=0 else -1)

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

ans = 10 ** 7
for i in range(2 ** n):
    TCA = [0 for i in range(m + 1)]
    f = 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            TCA = [x + y for (x, y) in zip(TCA, CA[j])]
        else:
            pass
    for j in range(1, m + 1):
        if TCA[j] < x:
            f = 1
            break
        else:
            pass
    if f == 0:
        ans = min(ans, TCA[0])
    else:
        pass
if ans == 10 ** 7:
    print(-1)
else:
    print(ans)

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


ans=10**9
if min(np.sum(a, axis=0))<x:
  print(-1)
  sys.exit()
for i in range(2**n):
  l=list(bin(i)[2:].zfill(n))
  
  a_sum=np.array([0]*m)
  cost=0
  for j in range(n):
    if l[j]=='1':
      a_sum+=a[j]
      cost+=c[j]
  
  if min(a_sum)>=x:
    ans=min(ans,cost)
print(ans)

Solution (Python):
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    m = kwargs["m"]
    x = kwargs["x"]
    C = kwargs["C"]
    A = kwargs["A"]
    res = -1

    for i in range(2 ** n):
        l = [j for j in '{0:0{1}b}'.format(i, n)]
        scores = [0 for i in range(m)]
        price = 0

        for j in range(n):
            if l[j] == '1':
                for k in range(m):
                    scores[k] += A[j][k]

                price += C[j]

        if min(scores) >= x:
            if res == -1:
                res = price

            res = min(res, price)

    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"], kwargs["m"], kwargs["x"] = [int(i) for i in cin]

    kwargs["C"] = []
    kwargs["A"] = []
    for i in range(kwargs["n"]):
        cin = input().split()
        c = [int(i) for i in cin][0]
        a = [int(i) for i in cin][1:]
        kwargs["C"].append(c)
        kwargs["A"].append(a)

    cout = main(kwargs)
    print(cout)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n,m,x=mii()
chk=False
ansmoney=10**100
c=[]
arr=[]

for i in range(n):
    mat=limii()
    c.append(mat[0])
    arr.append(mat[1:])

for i in product([0,1],repeat=n):
    total=0
    chkarr=[0]*m
    for j in range(n):
        if i[j]==1:
            total+=c[j]
            for k in range(m):
                chkarr[k]+=arr[j][k]
            
    
    cnt=0
    for p in range(m):
        if chkarr[p]>=x:
            cnt+=1
    if cnt==m:
        chk=True
        ansmoney=min(ansmoney,total)
if chk:
    print(ansmoney)
else:
    print(-1)

Solution (Python):
import itertools

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

ans = (10 ** 5) * 12 + 1

for choose in itertools.product([0,1], repeat=N):
    cnt_ca = 0
    ability = [0] * M
    money = 0
    for c in choose:
        if c == 1:
            money += CA[cnt_ca][0]
            for i in range(M):
                ability[i] += CA[cnt_ca][i+1]
        cnt_ca += 1
    if min(ability) >= X:
        ans = min(ans,money)

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

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

N, M, X = map(int, input().split())
C = [None]*N
A = [None]*N
for i in range(N):
    line = list(map(int, input().split()))
    C[i] = line[0]
    A[i] = np.array(line[1:])

choose = [True, False]

min_price = -1

for books in product(choose, repeat=N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if books[i]:
            knowledge += A[i]
            price += C[i]
    if np.any(knowledge < X):
        continue
    if min_price == -1:
        min_price = price
    min_price = min(min_price, price)

if min_price == -1:
    print(-1)
else:
    print(min_price)

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

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

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

ans = np.inf

for i in range(2**N):
    point = np.zeros(M)
    cost = 0

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

    if np.all(point >= X):
        ans = min(ans, cost)

if ans != np.inf:
    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())))

cost = 10**18
for i in range(2**n):

    i = format(i,'0{}b'.format(n))

    flg =0
    total =0
    skill=[0]*m
    for j in range(n):
        if i[j]=='1':
            book_j = books[j]
            
            total += book_j[0]

            for l in range(len(book_j)):
                if l==0:
                    continue
                else:
                    skill[l-1]+=book_j[l]

    for k in range(m):
        if skill[k]<x:
            flg+=1
    
    if flg==0:
        cost = min(cost,total)

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

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


for i in range(1,n+1):
    for k in itertools.combinations(range(n),i):
        tmp = 0
        exp = [0]*m
        for j in k:
            gold = False
            for i,a in enumerate(book[j]):
                if i==0:
                    tmp += a
                else:
                    exp[i-1] += a
        if min(exp) >= x:
            ans = min(ans,tmp)

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

Solution (Python):
from itertools import combinations

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

minn = float('inf')
idx = [i for i in range(n)]
for i in range(1, n + 1):
    for comb in combinations(idx, i):
        status = [0] * m
        money = 0
        for j in comb:
            money += ca[j][0]
            for i, ai in enumerate(ca[j][1:]):
                status[i] += ai
        if min(status) >= x:
            minn = min(minn, money)
print(-1 if minn > 10**9 else minn)

Solution (Python):
def is_valid(vals, M, X):
    for i in range(M):
        if vals[i] < X:
            return False
    return True

def solve(N, M, X, C, A):
    ret = float("inf")
    for i in range(2 ** N):
        tmp_vals = [0 for _ in range(M)]
        cost = 0
        for j in range(N):
            if (i >> j) & 1:
                cost += C[j]
                for k in range(M):
                   tmp_vals[k] += A[j][k]
        ret = min(ret, cost) if is_valid(tmp_vals, M, X) else ret
    return ret if ret != float("inf") else -1




if __name__ == '__main__':
    N, M, X = map(int, input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        C.append(tmp[0])
        A.append(tmp[1:])

    print(solve(N, M, X, C, A))

Solution (Python):
import itertools
n,m,x = map(int, input().split())
argo = list()
for i in range(n):
    argo.append(list(map(int, input().split())))
least = float("inf")
test = [x] * m
for i in range(1,n+1):
    tmp = list(itertools.combinations(argo, i))
    for j in range(len(tmp)):
        boolean = True
        money = 0
        check = [0] * m
        for k in range(i):
            money += tmp[j][k][0]
            for l in range(m):
                check[l] += tmp[j][k][l+1]
        for k in range(m):
            if check[k] < x:
                boolean = False
                break
        if boolean:
            if money <= least:
                least = money
if least == float("inf"):
    print(-1)
else:
    print(least)

Solution (Python):
N,M,X = map(int,input().split())
C = [0]*N
A = [[0] for _ in range(N)]
for i in range(N):
    tmp = list(map(int,input().split()))
    C[i] = tmp[0]
    A[i] = tmp[1:M+1]
f = False
money_min = 100000000000
for i in range(1,2**N):
    use = format(i,"0{}b".format(N))
    money = 0
    understand = [0]*M
    for j in range(N):
        if use[j] == "1":
            money += C[j]
            for k in range(M):
                understand[k] += A[j][k]
    if min(understand) >= X and money < money_min:
        money_min = money
        f = True

if f:
    print(money_min)
else:
    print(-1)

Solution (Python):


import numpy as np

N,M,X = list(map(int, input().split()))
prices = []
As = np.zeros((N,M+1), dtype=int)

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

queue = []

def f(id, price, skill):
    
    
    if skill.min()>=X:
        
        return price
    else:
        if id >= N:
            return np.inf
        else:
            return min(f(id+1, price+As[id,0], skill + As[id, 1:]), f(id+1, price, skill))

ans = f(0,0,np.zeros(M))
if ans == np.inf:
    print(-1)
else:
    print(ans)

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

    ans = 10 ** 7
    for i in range(2 ** 12):
        money = 0
        skills = np.zeros(m)
        for j in range(n):
            if ((i >> j) & 1):
                money += books[j][0]
                skills += books[j][1:]
        if (skills >= x).all():
            ans = min(ans, money)

    if ans == 10 ** 7:
        print(-1)
        return
    print(ans)
    
resolve()

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


ans = float("inf")
for p in itertools.product([0,1],repeat = N):
    cost = 0
    algo = [0]*M
    for i in range(N):
        if p[i]:
            cost += CAs[i][0]
            for j in range(M):
                algo[j] += CAs[i][j+1]
    for a in algo:
        if a < X:
            break
    else:
        ans = min(ans,cost)

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

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

costs = []
arrays = []
for _ in range(N):
    arr = tuple(map(int, input().split()))
    costs.append(arr[0])
    arrays.append(arr[1:])

total_costs = []
for i in range(1, 2**N):
    total_cost = 0
    selected_arrays = [] 
    for j in range(0, N):
        if (i >> j)&1:
            total_cost += costs[j]
            selected_arrays.append(arrays[j])
            
    rikais = [0] * M
    for arr in selected_arrays:
        for i, a in enumerate(arr):
            rikais[i] += a

    if all(map(lambda r: r>=X, rikais)):
        total_costs.append(total_cost)

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

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


def main():
    n, m, x = list(map(int, input().split()))
    A = np.array([list(map(int, input().split())) for _ in range(n)])
    cost = []
    for i in range(n):
        combs = combinations(range(n), i+1)
        for comb in combs:
            A2 = np.array([A[c] for c in comb])
            A2sum = np.sum(A2, axis=0)
            if (A2sum[1:] >= x).all():
                cost.append(A2sum[0])

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




if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

lst = []

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


min_num = float("inf")
for i in range(N):
    a = itertools.combinations([i for i in range(N)], i+1)

    for j in a:
        tmp = [0 for _ in range(M)]
        for k in j:
            for r in range(M):
                tmp[r] += lst[k][r+1]
        for t in tmp:
            if t < X:
                break
        else:
            cnt = 0
            for c in j:
                cnt += lst[c][0]
            if cnt <= min_num:
                min_num = cnt

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

Solution (Python):
import itertools as itt
def resolve():
    N,M,X = map(int,input().split())
    CA = [list(map(int,input().split())) for i in range(N)]
    mxc = float('inf')
    for r in range(N+1):
        for cmb in itt.combinations(CA,r):
            cost = 0
            tbl = [0]*M
            for x in cmb:
                cost+=x[0]
                for i in range(M):
                    tbl[i]+= x[i+1]

            for i in tbl:
                if i < X:
                    break
            else:
                mxc = min(cost,mxc)
                
    if mxc == float('inf'):
        print(-1)
    else:
        print(mxc)



if __name__ == "__main__":
    resolve()

Solution (Python):
from itertools import combinations

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

ans = float('inf')
for i in range(1, n+1):
    for c_books in combinations(books, i):
        scores = [0] * m
        price = 0
        for book in c_books:
            price += book[0]
            for j in range(m):
                scores[j] += book[j+1]
        if all([scores[k] >= x for k in range(m)]):
            ans = min(ans, price)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

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

C = [1 for i in range(N)]
A = [[0 for i in range(M)] for j in range(N)]

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

    C[i], A[i] = input_[0], input_[1:]

price_min = 10 ** 9
for pattern in range(2 ** N):
    price_sum = 0
    skill_levs = [0 for i in range(N)]

    pattern = str(bin(pattern)).lstrip('0b').zfill(N)

    for idx, p in enumerate(pattern):
        if p == '1':
            price_sum += C[idx]
            skill_levs = [lev + up for lev, up in zip(A[idx], skill_levs)]
    if min(skill_levs) >= X:
        price_min = min(price_min, price_sum)

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

Solution (Python):
import numpy as np

n, m, x = map(int, input().split())
a = []
cost_lst = []
for _ in range(n):
    lst = (list(map(int, input().split())))
    cost_lst.append(lst.pop(0))
    a.append(lst)
data = np.array(a)

min_cost = 9999999999

for i in range(2 ** n):
    b = np.zeros(m)
    cost = 0
    num = i
    for j in range(n):
        if num % 2 == 0:
            b += data[j]
            cost += cost_lst[j]
        num = num // 2
    for skill in b:
        if skill < x:
            break
    else:
        min_cost = min(min_cost, cost)

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

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

l = []

def f(cs, i, a):
    for j in range(n - i - 1):
        cs2 = cs + caas[i + j + 1][0]
        a2 = [y + a[k] for k, y in enumerate(caas[i + j + 1][1:])]
        if min(a2) >= x:
            l.append(cs2)
        else:
            f(cs2, i + j + 1, a2)

f(0, -1, [0 for _ in range(m)])

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

Solution (Python):
from itertools import combinations

import numpy as np


def run():
    n, m, x = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(n)]
    c = np.array([d[0] for d in data])
    a = np.array([d[1:] for d in data])

    candidates = []
    for buy_num in range(1, n + 1):
        for comb in combinations(range(n), buy_num):
            temp_a = a[comb, :]

            sum_a = np.sum(temp_a, axis=0)

            if np.all(sum_a >= x):
                sum_c = np.sum(c[list(comb)])
                candidates.append(sum_c)

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


if __name__ == '__main__':
    run()

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)



INF = float("inf")
MOD = 10 ** 9 + 7


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

ans = INF
for s in (range(1 << N)):
    A = defaultdict(int)
    cost = 0
    for i in range(N):
        if s >> i & 1:
            book = books[i]
            cost += book[0]
            for i in range(1, M + 1):
                A[i] += book[i]
    ok = True
    for i in range(1, M + 1):
        if A[i] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)

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

Solution (Python):
import sys

N, M, X = map(int, sys.stdin.readline().strip().split())

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

ans = float('inf')

for i in range(2 ** N):
    bit = [(i >> j) & 1 for j in range(N)]  

    understand = [0] * M
    for i, b in enumerate(bit):
        if b != 0:
            
            understand = [x + y for x, y in zip(A[i], understand)]

    if min(understand) >= X:
        cost = [c * b for c, b in zip(C, bit)]
        ans = min(sum(cost), ans)

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 = list(map(int,input().split()))
    c[i] = A[0]
    a[i] = A[1:]

t = [0] * m
for i in range(n):
    for j in range(m):
        t[j] += a[i][j]
if(min(t) < x):
    print(-1)
    exit()
mi = sum(c) + 1
for i in range(2**n):
    cost = 0
    sk = [0] * m
    for j in range(n):
        y = 2**j
        if(i & y != 0):
            cost += c[j]
            for k in range(m):
                sk[k] += a[j][k]
    if(min(sk) >= x):
        mi = min(mi,cost)
print(mi)

Solution (Python):
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]
res = n*(10**5)+1
for i in range(2**n-1):
    s = format(i+1, '0'+str(n)+'b')
    und = [0]*m
    mon = 0
    for j in range(n):
        if s[j] == '0':
            continue
        else:
            for c in range(m):
                und[c] += ca[j][c+1]
            mon += ca[j][0]
    if min(und) >= x:
        res = mon if mon < res else res
if res == n*(10**5)+1:
    res = -1
print(res)

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

c = []
d = []
for i in range(n):
	s = list(map(int, input().split()))
	
	
	d.append(s)
ans = 10**9
for i in range(1,n+1):
	for j in itertools.combinations(d,i):
		s = [0 for ii in range(m+1)]
		for k in j:
			for l in range(m+1):
				s[l] += k[l]
		y = min(s[1:])
		if y >= x:
			ans = min(ans,s[0])
if ans == 10**9:
	print (-1)
else:
	print (ans)

Solution (Python):
import numpy as np

N, M, X = map(int, input().split())
CA = []
for _ in range(N):
    Ci, *A = map(int, input().split())
    CA.append((Ci, A))

ans = 10**8
studied = np.array([0] * M)

for i in range(2**N):
    flag = True
    tmp_ans = 0
    studied = np.array([0] * M)
    for j in range(N):
        if i >> j & 1:
            tmp_ans += CA[j][0]
            studied += CA[j][1]
    for study in studied:
        if study < X:
            flag = False
            break
    if flag:
        ans = min(ans, tmp_ans)

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

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, M, X = map(int, input().split())
costs = []
effects = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    costs.append(tmp[0])
    effects.append(tmp[1:])

ans = INF
for i in range(1<<N):
    total_costs = 0
    algo = [0] * M
    for k in range(N):
        if 1&i>>k:
            total_costs += costs[k]
            for j, effect in enumerate(effects[k]):
                algo[j] += effect
    is_ok = True
    for a in algo:
        if a < X:
            is_ok = False
            break
    if is_ok:
        ans = min(ans, total_costs)

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

Solution (Python):
from itertools import combinations
import numpy as np
n,m,x = map(int,input().split())
money_ls = [0] * n
ex_ls = [0] * n
for i in range(n):
    in_ = list(map(int, input().split()))
    money_ls[i] = in_[0]
    ex_ls[i] = in_[1:]

min_money = float('inf')


book_ls = [i for i in range(n)]
for num in range(1,n+1):
    for inds in combinations(book_ls, num):
        res = True
        money = 0
        ex_now = [0] * m
        for ind in inds:
            money += money_ls[ind]
            for i in range(m):
                ex_now[i] += ex_ls[ind][i]
        for i in range(m):
            if ex_now[i] < x:
                res = False
        if res:
            min_money = min(money, min_money)
if min_money == float('inf'):
    min_money = -1
print(min_money)

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


ans = 10000000000000
for j in range(m):
    val = 0
    for i in range(n):
        val += a[i][j]
    
    if val < x:
        print('-1')
        exit()
for i in range(2 ** n):
    flg = [True] * n
    for j in range(n):
        if i >> j & 1:
            flg[j] = False
    flg2 = True
    for j in range(m):
        val = 0
        for k in range(n):
            if flg[k] == False:
                continue
            val += a[k][j]
        
        if val < x:
            flg2 = False
    if flg2 == True:
        val = 0
        for j in range(n):
            if flg[j] == True:
                val += c[j]
        ans = min(ans,val)
    
print(ans)

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

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

ans = 10**10
for j in range(1 << n):
    flg = True
    for i in range(1, m+1):
        x1 = 0
        for k in range(n):
            a = books[k][i]
            if j & (1 << k):
                x1 += a

        if x1 < x:
            flg = False
            break
    if not flg:
        continue

    ans1 = 0
    for k in range(n):
        c = books[k][0]
        if j & (1 << k):
            ans1 += c

    ans = min(ans, ans1)

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

Solution (Python):
from itertools import chain,combinations
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def isOverX(X, CA, M):
    s = [0] * (M + 1)
    for ca in CA:
        for i, a in enumerate(ca):
            s[i] += a
    if min(s[1:]) >= X:
        return s[0]
    else:
        return -1
def main():
    N, M, X = map(int, input().split())

    CA = []
    for i in range(N):
        CA.append(list(map(int, input().split())))
    
    ans = 10 ** 10
    ok = False
    for ca in powerset(CA):
        cost = isOverX(X, list(ca), M)
        if cost != -1:
            ans = min(ans, cost)
            ok = True
    print(ans if ok else -1)

if __name__ == '__main__':
    main()