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 = [int(v) for v in input().strip().split(" ")]

C = []
A = []
for _ in range(N):
    items = [int(v) for v in input().strip().split(" ")]
    C.append(items[0])
    A.append(items[1:])


selection = []


class Solution():
    def __init__(self, N, M, X, A, C):
        self.N = N
        self.M = M
        self.X = X
        self.A = A
        self.C = C
        self.min_cost = sum(self.C) + 100


    def search(self, from_index, selection=None):
        if from_index < self.N:
            for i in range(from_index, self.N):
                s = selection + [i]
                result = self.search(from_index=i + 1, selection=s)
                if result != -1:
                    if result < self.min_cost:
                        self.min_cost = result
            this_result = self.search(from_index=self.N, selection=selection)
            if this_result != -1:
                if this_result < self.min_cost:
                    self.min_cost = this_result
            return self.min_cost
        else:
            XX = [self.X] * self.M
            for s in selection:
                for j in range(self.M):
                    XX[j] -= self.A[s][j]

            success_flag = True
            for x in XX:
                if x > 0:
                    success_flag = False
                    break

            if success_flag:
                money = 0
                for s in selection:
                    money += self.C[s]
                return money
            else:
                return -1

s = Solution(N, M, X, A, C)

result = s.search(from_index=0, selection=selection)
if result == sum(C) + 100:
    print(-1)
else:
    print(result)

Solution (Python):
N, M, X = [int(v) for v in input().strip().split(" ")]

C = []
A = []
for _ in range(N):
    items = [int(v) for v in input().strip().split(" ")]
    C.append(items[0])
    A.append(items[1:])


selection = []


class Solution():
    def __init__(self, N, M, X, A, C):
        self.N = N
        self.M = M
        self.X = X
        self.A = A
        self.C = C
        self.min_cost = sum(self.C) + 100


    def search(self, from_index, selection=None):
        if from_index < self.N:
            for i in range(from_index, self.N):
                s = selection + [i]
                result = self.search(from_index=i + 1, selection=s)
                if result != -1:
                    if result < self.min_cost:
                        self.min_cost = result
            this_result = self.search(from_index=self.N, selection=selection)
            if this_result != -1:
                if this_result < self.min_cost:
                    self.min_cost = this_result
            return self.min_cost
        else:
            XX = [self.X] * self.M
            for s in selection:
                for j in range(self.M):
                    XX[j] -= self.A[s][j]

            success_flag = True
            for x in XX:
                if x > 0:
                    success_flag = False
                    break

            if success_flag:
                money = 0
                for s in selection:
                    money += self.C[s]
                return money
            else:
                return -1

s = Solution(N, M, X, A, C)

result = s.search(from_index=0, selection=selection)
if result == sum(C) + 100:
    print(-1)
else:
    print(result)

Solution (Python):
import numpy as np
import itertools
N, M, X = (int(i) for i in input().split())
Y = np.zeros((N, M+1))
for i in range(N):
    Y[i,:] = [int(i) for i in input().split()]
C = Y[:,0]
A = np.matrix(Y[:,1:])
res = np.inf
f = '0'+str(N)+'b'
for i in range(2**N):
    z = np.array([int(s) for s in list(format(i, f))])
    cost = z @ C
    skill = z * A
    if (skill >= X).all() and (cost < res):
        res = cost
if np.isinf(res):
    print(-1)
else:
    print(int(res))

Solution (Python):
import itertools
N,M,X = map(int, input().split())
S = []
N_list = list(range(1,N+1))
for _ in range(N):
    c = list(map(int, input().split()))
    S.append(c)
min = 1200001
for i in range(1,N+1):
    c = list(itertools.combinations(N_list, i))
    for v in c:
        A = [0]*M
        money = 0
        flag =0
        for i in range(len(v)):
            book = v[i]
            book_list = S[book-1]
            money += book_list[0]
            for t in range(M):
                A[t] += book_list[t+1]
        for s in A:
            if s<X:
                flag = 1
                break
        if flag == 0:
            if money <= min:
                min = money

if min == 1200001:
    print(-1)
else:
    print(min)

Solution (Python):
import itertools
import numpy as np
N,M,X = (int(x) for x in input().split())
S = []
C = []
l = []
ans = 10000000
for i in range(N):
  l.append(i)
for i in range(N):
  s = [int(x) for x in input().split()]
  S.append(s)
npS = np.array(S)

for i in range(1,N+1):
  if i == 1:
    continue
  C =  list(itertools.combinations(l,i)) + C

for i in C:
  wa = np.zeros(M+1)
  
  for j in range(len(i)):
   
    wa = wa + S[i[j]]
  
  cnt = 0
 
  for k in range(0,len(wa)):
    if k == 0:
      continue
    if wa[k] >= X:
      cnt += 1
   
    if cnt == M and ans > wa[0]:
      ans = wa[0]
for i in range(N):
  cnt = 0
  for j in range(M+1):
    if j == 0:
      continue
    if S[i][j] >= X:
      cnt += 1
    if cnt == M and ans > S[i][0]:
      ans = S[i][0]
if ans == 10000000:
  print(-1)
else:
  print(int(ans))

Solution (Python):
import itertools
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]
cnt = [i for i in range(n)]
ans = 10**12
ok = False
for i in range(1,n+1):
    for conb in itertools.combinations(cnt, i):
        z = [0]*(m+1)
        for j in conb:
            for k in range(m+1):
                z[k] = z[k] + ca[j][k]
            if sum(l >= x for l in z[1:]) == m:
                ans = min(ans, z[0])
                ok = True
if ok:
    print(ans)
else:
    print(-1)

Solution (Python):
import itertools

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

minnum = (10**5) * 13

for i in range(1, n + 1):
    tmp = list(itertools.combinations(c, i))
    
    for item in tmp:
        t = list(zip(*item))
        xs = [sum(t[j]) if sum(t[j]) >= x else False for j in range(1, m + 1)]
        if False not in xs and sum(t[0]) < minnum:
            minnum = sum(t[0])
if minnum != (10**5) * 13:
    print(minnum)
else:
    print(-1)

Solution (Python):
from itertools import combinations
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:])
del tmp
costs = []
for i in range(1, N + 1):
    comb_idx = combinations(range(N), i)
    for indices in comb_idx:
        sub_A = [A[idx] for idx in indices]
        sub_C = [C[idx] for idx in indices]
        sum_sub = [0] * M
        for row in sub_A:
            for j, v in enumerate(row):
                sum_sub[j] += v
        if all(X <= v for v in sum_sub):
            costs.append(sum(sub_C))
if costs:
    print(min(costs))
else:
    print(-1)

Solution (Python):
import itertools
import numpy as np

n, m, x= map(int, input().split())
a = [input().split() for l in range(n)]
npa=np.array(a, dtype=int)

hon=-1
for i in range(1,n+1):
  base = list(itertools.combinations(range(0,n),i))

  
  for j in base:
    totalv=np.sum(npa[j,], axis=0)

    
    if (min(totalv[1:m+1]) >= x):
      if (hon == -1): hon=totalv[0]
      if (hon >= totalv[0]): hon=totalv[0]

      
print (hon)

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

C=[0] * N
A=[0] * N

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

n=0
s=100000000

for i in range(2**N):
  score=[0]*M
  s_tmp=0
  for j in range(N):
    if ((1 << j) & i) >> j == 1:
      s_tmp+=C[j]
      for k in range(M):
        score[k]+=A[j][k]
  flg=1
  for k in range(M):
    if score[k] < X:
      flg=0
      break
  if flg==1:
    if s_tmp < s:
      s=s_tmp
if s == 100000000:
  print(-1)
else:
  print(s)

Solution (Python):
from itertools import chain, combinations


def powerset(iterable):
    s = list(iterable)
    sets = list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))
    sets = [s for s in sets if len(s) > 0]
    return sets

def check_row(row, x):
    for el in row:
        if el < x:
            return False
    return True

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

result = float("inf")
sets = powerset([i for i in range(n)])

for s in sets:
    k_rows = [0 for i in range(m)]

    cost = 0
    for idx in s:
        cur_c_k = c_k_table[idx]
        cost += cur_c_k[0]

        k_row = list(cur_c_k[1:])
        for i in range(m):
            k_rows[i] += k_row[i]
    
    if check_row(k_rows, x):
        result = min(result, cost)
if result == float("inf"):
    print(-1)
else:
    print(result)

Solution (Python):
import bisect
import collections
import heapq
import math
import operator as op
from collections import Counter
from functools import reduce

import numpy as np


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def main():
    N, M, X = get_inputs(int)
    Cs = np.empty(N, dtype=np.int)
    A_mat = np.empty((N, M), dtype=np.int)
    for i in range(N):
        CAs = get_inputs(int)
        Cs[i] = CAs[0]
        for j in range(M):
            A_mat[i, j] = CAs[j+1]
    
    

    
    if (np.sum(A_mat, axis=0) >= X).all():
        def dfs(i, As_cur, C_cur):
            
            As_buy = As_cur + A_mat[i, :]
            C_buy = C_cur + Cs[i]
            if (As_buy >= X).all():
                
                
                pass
            else:
                if i < N-1:
                    C_buy = dfs(i+1, As_buy, C_buy)
                else:
                    C_buy = float("inf")

            
            if i < N-1:
                C_dontbuy = dfs(i+1, As_cur, C_cur)
            else:
                C_dontbuy = float("inf")

            return min(C_buy, C_dontbuy)

        ans = dfs(0, np.zeros(M, dtype=np.int), 0)
        assert ans != float("inf")
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

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

c = [0] * (n)
a = [0] * (n)

ans = 0

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

a_rev = list(zip(*a))
for i in range(len(a_rev)):
  if sum(a_rev[i]) < x:
    print("-1")
    exit()


min_cost = sum(c)

num = len(a)
for i in range(2 ** num):
  bag = []
  bag_skill = []
  for j in range(num):
    if ((i >> j) & 1):
      
      
      bag.append(c[j])
      bag_skill.append(a[j])

  
  bag_skill = list(zip(*bag_skill))
  now = 0
  for k in range(len(bag_skill)):
    if sum(bag_skill[k]) >= x:
      now += 1
      
    if now == len(bag_skill):
      cost = sum(bag)
      if cost < min_cost:
        min_cost = cost
  
print(min_cost)

Solution (Python):
n,m,x=map(int,input().split())
cas=[list(map(int,input().split())) for _ in range(n)]
ans=float('inf')
for i in range(1, 2**n):
    v=0
    us=[0]*m
    for b,ca in zip(bin(i)[2:].zfill(n), cas):
        b=int(b)
        if b==0:
            continue
        v+=ca[0]
        for j,a in enumerate(ca[1:]):
            us[j]+=a
    for u in us:
        fg=0
        if u<x:
            fg=1
            break
    if fg==0:
        ans=min(ans,v)
if i==2**n-1 and fg==1:
    print(-1)
    exit()
print(ans)

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

S = 10**10

for i in range(2**N):
    B = [0 for m in range(M+1)]
    SS = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(1,M+1):
                B[k] += A[j][k]
            SS += A[j][0]
    flag = True
    for k in range(1,M+1):
        if B[k] < X:
            flag = False
    if flag and SS < S:
        S = SS

if S == 10**10:
    print('-1')
else:
    print(str(S))

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

perms=[]
for i in range(2**n):
    list2 = []
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(1)
        else:
            list2.append(0)
    perms.append(list2)

oks=[]
for i in perms:
    cost = 0
    xs = [0]*m
    for idx,j in enumerate(i):
        if j==1:
            cost+=books[idx][0]
            for k in range(m):
                xs[k]+=books[idx][k+1]
    if min(xs)>=x:
        oks.append(cost)

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

Solution (Python):
n,m,x = map(int, input().split())
ca = []
for i in range(n):
    ca.append(list(map(int,input().split())))
ans = -1
for i in range(1, 1<<n):
    tmp_ca = [0] * len(ca[0])
    for j in range(n):
        if (i>>j)&1:
            tmp_ca[0] += ca[j][0]
            for k in range(len(tmp_ca) - 1):
                tmp_ca[k+1] += ca[j][k+1]
    ok_num = 0
    for j in range(len(tmp_ca) - 1):
        if tmp_ca[j+1] >= x:
            ok_num += 1
    if ok_num == m:
        if ans == -1:
            ans = tmp_ca[0]
        else:
            ans = min(ans, tmp_ca[0])
print (ans)

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

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



ans = float("inf")
for i in range(2 ** n):
    skill = [0] * (m+1)
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m+1):
                skill[k] += A[j][k]


    

    if skill:
        for i in range(1, m+1):
            if x > skill[i]:
                break
        else:
            ans = min(ans, skill[0])

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

Solution (Python):
N,M,X = map(int, input().split())
CA_s = [list(map(int, input().split())) for _ in range(N)]
ans = 10**18
pattern = []
for i in range(2 ** (N)):
    tmp = [False] * N
    for j in range(N):
        if i >> j & 1:
            tmp[j] = True
    price = 0
    rikaidos = [0] * M
    for i in range(len(tmp)):
        if(tmp[i] == True):
            for j in range(M+1):
                if j == 0:
                    price += CA_s[i][0]
                else:
                    rikaidos[j-1] += CA_s[i][j]
    if len(list(filter(lambda x:x<X, rikaidos)))==0 and price<ans:
        ans = price
if ans == 10**18:
    ans = -1
print(ans)

Solution (Python):
from itertools import combinations

n,m,x = [int(i) for i in input().split()]
data = [input() for _ in range(n)]
data = [[int(i) for i in d.split()] for d in data]

min_total = -1
for m_comb in range(1, n+1):
    for comb in combinations(data, m_comb):
        c_totals = [sum([c[i] for c in comb]) >= x for i in range(1, m+1)]
        if all(c_totals):
            if min_total == -1:
                min_total = sum([c[0] for c in comb])
            if sum([c[0] for c in comb]) < min_total:
                min_total = sum([c[0] for c in comb])
print(min_total)

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, X = read_ints()
    A = []
    for _ in range(N):
        A.append(read_ints())

    min_T = math.inf
    for S in range(1, (1<<N)):
        T = [0]*(M+1)
        for i in range(0, N):
            if (S>>i)&1 == 1:
                for j in range(M+1):
                    T[j] += A[i][j]
        if all(t >= X for t in T[1:]) and T[0] < min_T:
            min_T = T[0]
    if min_T == math.inf:
        return -1
    return min_T


if __name__ == '__main__':
    print(solve())

Solution (Python):
import itertools

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

ans = []
for n in range(N):
    all_list = itertools.combinations(range(N), n+1)
    for c in all_list:
        scores = [0 for _ in range(M)]
        price = 0
        for i in c:
            for j in range(M):
                scores[j] += A[i][j]
            price += C[i]
        clear = True
        for j in range(M):
            if scores[j] < X:
                clear = False
        if clear:
            ans.append(price)

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

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

import numpy as np

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


for n in range(2**N):
  ls = [0] * (M+1)
  bin = format(n,'b').zfill(N)
  for i in range(N):
    ls = np.array(ls) + np.array(C[i])*int(bin[i])

  if min(ls[1:]) >= X:
    if ls[0] < ans:
      ans = ls[0]

      
if ans < N * (10**5)+1:
  print(ans)
else:
  print(-1)

Solution (Python):
n, m, x = map(int, input().split())
r = []
for _ in range(n):
    r.append(list(map(int, input().split())))
r_all = [0 for i in range(m+1)]
for i in range(m+1):
    for j in range(n):
        r_all[i] += r[j][i]
def d(r_sum):
    achieved = True
    for u in r_sum[1:]:
        if u < x:
            achieved = False
    return achieved
if d(r_all) == False:
    print(-1)
else:
    ans = r_all[0]
    for i in range(2**n):
        r_sum = [0 for i in range(m+1)]
        buy = '0' * (n-(len(bin(i))-2))+bin(i)[2:]
        for j in range(n):
            if buy[j] == "1":
                for k in range(m+1):
                    r_sum[k] += r[j][k]
        if d(r_sum) == True and r_sum[0] < ans:
            ans = r_sum[0]
    print(ans)

Solution (Python):
import itertools
N, M, X = map(int, input().split())
C = []
A = dict()
for i in range(N):
    CA = list(map(int, input().split()))
    C.append(CA[0])
    for j in range(1, M+1):
        if j in A:
            A[j].append(CA[j])
        else:
            A[j] = [CA[j]]

cost = float("inf")

for i in range(1, N+1):
    for pm in itertools.combinations(list(range(1, N+1)), r=i):
        c = 0
        k = dict()
        for p in pm:
            c += C[p-1]

            for m in range(1, M+1):
                if m in k:
                    k[m] += A[m][p - 1]
                else:
                    k[m] = A[m][p - 1]

        if min(k.values()) >= X:
            cost = min(cost, c)


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

Solution (Python):



def search(idx, ra, pr):
    if idx >= n:
        if min(ra) >= x:
            return pr
        else:
            return 10**9
    else:
        
        w_ra = list()
        for j in range(m):
            w_ra.append(ra[j] + ca[idx][j+1])
        
        a1 = search(idx+1, w_ra, pr+ca[idx][0])
        
        a2 = search(idx+1, ra, pr)
        
        if a1 == 10**9 and a2 == 10**9:
            return 10**9
        elif a1 == 10**9:
            return a2
        elif a2 == 10**9:
            return a1
        else:
            return min(a1, a2)


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

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

minpr = 10**9

wkl = [0] * m
minpr =search(0, wkl, 0)
if minpr == 10**9:
    minpr = -1

print(minpr)

Solution (Python):
import numpy as np
import itertools

N, M, X = map(int, input().split())
C_list = []
ans = []

for _ in range(N):
    C_list.append(list(map(int, input().split())))
    
for i in range(1,N+1):
    for j in itertools.combinations(C_list, i):
        a = np.zeros(M+1)
        for k in j:
            a += np.array(k)
        if np.all(a[1:]>=X):
            ans.append(a[0])
if ans:
    print(int(min(ans)))
else:
    print(-1)

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

ans = [[0 for i in range(m+1)] for j in range(2**n)]
b = []
count = 0
for i in range(2 ** n):
    tmp = []
    for j in range(n):  
        if ((i >> j) & 1):
            tmp = L[j]  
            for k in range(m+1):
                ans[i][k] = ans[i][k] + tmp[k]

    check = 1
    for k in range(1,m+1):
        if ans[i][k] < x:
            check = 0
    if check:
        b.append(ans[i])


if len(b) == 0:
    print("-1")
else:
    b.sort()
    print(b[0][0])

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

N, M, X = map(int, input().split())
C = []
A = []

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

patterns = []

def dfs(buyable, pattern, idx):
    copy = pattern[:]
    if len(copy) == buyable:
        patterns.append(copy)
    elif idx == N:
        return
    else:
        dfs(buyable, copy, idx+1)
        copy.append(idx)
        dfs(buyable, copy, idx+1)

achived = False
_min = sum(C)
for i in range(1, N+1):
    patterns = []
    dfs(i, [], 0)

    for pattern in patterns:
        total = 0
        tmp = [0 for i in range(M)]
        for j in pattern:
            total += C[j]
            for k in range(M):
                tmp[k] += A[j][k]

        if min(tmp) >= X and _min >= total:
            _min = total
            achived = True

if achived:
    print(_min)
else:
    print(-1)

Solution (Python):
import itertools
n,m,x = list(map(int,input().split()))
a = []
f = True
res = []
p = 0

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

for k in range(n):
    for i in itertools.combinations(a,k+1):

        f = True
        for l in range(m):
            if f == True:
                c = 0
                p = 0
                for j in range(k+1):
                    if len(i) == 1:
                        c += i[j][l+1]
                    else:
                        c += i[j][l+1]
                if c < x:
                    f = False
           
        if f == True:
            ressum = 0
            for o in range(k+1):
                ressum += i[o][0]
            res.append(ressum)

if res == []:
    print(-1)
else:
    print(min(res))

Solution (Python):
from itertools import combinations

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

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

array = [i for i in range(N)]
comb = []

for i in range(N):
    r = list(map(list,list(combinations(array,i+1))))
    comb.extend(r)

ans = []

for i in comb:
    check = [0 for i in range(M)]
    answer = [0 for i in range(M+1)]
    for j in i:
        for m in range(len(all_text[j])):
            answer[m] += all_text[j][m]
            if m>=1 and answer[m] >= X:
                check[m-1] = 1
    if sum(check) >= M:
        ans.append(answer[0])

if not ans:
    print(-1)
    exit()

ans.sort()
print(ans[0])

Solution (Python):
import itertools

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

ans = 10**10
for num in range(N):
    
    comb = list(itertools.combinations(enumerate(C), num + 1))
    for vals in comb:
        
        sum_c = 0
        l = [0 for _ in range(M)]
        for idx, c in vals:
            A = As[idx]
            for j in range(len(A)):
                l[j] += A[j]
            sum_c += c
        if min(l) >= X:
            ans = min(sum_c, ans)

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

Solution (Python):
n,m,x = map(int,input().split())
Inf = 10**10
c = [0]*n
a= []
for i in range(n):
  y =  list(map(int,input().split()))
  c[i] = y.pop(0)
  a += [y]




def f(i=0, s=[0]*m, p=0):
  if i == n and min(s) >= x:
    
    
    return p
  elif i == n and min(s) < x:
    return Inf
  else:
    return min(f(i+1,s,p),f(i+1,[s[j]+a[i][j] for j in range(m)],p+c[i]))
  

ans = f()
if ans == Inf:
  ans = -1
print(ans)

Solution (Python):
import numpy as np
n,m,x = map(int,input().split())
l = []
for i in range(n):
    l.append(np.array(input().split(),dtype=int)) 
import itertools
num = [i for i in range(n)]
min = 1000000000000000000000000
k = 1
while k <n+1:
    a = list(itertools.combinations(num, k))
    for i in range(len(a)):
        total =np.zeros(m+1,dtype=int)
        for j in range(len(a[i])):
            total +=l[a[i][j]]
        if np.sum(np.where(total < x)[0]) <=0:
            if min > total[0]:
                min = total[0]
                
    k +=1
if min == 1000000000000000000000000:
    print(-1)
else:
    print(min)

Solution (Python):
import sys;input=lambda:sys.stdin.readline().rstrip();ints=lambda:list(map(int,input().split()))
import numpy as np;from itertools import combinations

def main():
    n,m,x=ints()
    ca,val=[],[]
    for _ in range(n):
        inp=ints()
        ca.append(inp)
        flg=1
        for i in range(1,m+1):
            if inp[i]<x:
                flg = 0
        val.append(inp[0]) if flg==1 else None
    for num in range(2,n+1):
        for v in combinations(ca,num):
            vnp = np.array(v)
            s=vnp.sum(axis=0)
            flg=1
            for i in range(1,m+1):
                if s[i]<x:
                    flg = 0
            val.append(s[0]) if flg==1 else None
    print(-1 if not val else min(val))

if __name__ == '__main__':
    main()