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(' '))
cost = []
A = []

for _ in range(N):
    l = list(map(int, input().split(' ')))
    cost.append(l[0])
    A.append(l[1:])

ans = 10 ** 10

for state in range(1 << N):
    price = 0
    compre = [0 for _ in range(M)]
    for i in range(N):
        if ((state >> i) & 1) == 1:
            
            price += cost[i]
            for j in range(M):
                compre[j] += A[i][j]

    check = True
    for i in range(M):
        check &= (compre[i] >= X)
    if check:
        ans = min(ans, price)

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

Solution (Python):



import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect




import itertools

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

ans = float('inf')

for case in range(2**N):
    
    val = [0] * M
    price = 0
    
    for j in range(N):
        
        if case >> j & 1:
            price += data[j][0]
            for m in range(M):
                val[m] += data[j][m+1]

    flg = True
    for m in range(M):
        if val[m] < X:
            flg = False
    if flg:
        ans = min(ans, price)

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

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

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

def calc(p):
    cnt = np.dot(np.array(list(p)), np.array(A))
    return np.dot(np.array(list(p)), np.array(C)) if all(i >= X for i in cnt) else 10 ** 30

ans = 10 ** 30
for p in product(range(2), repeat=N):
    ans = min(ans, calc(p))

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

Solution (Python):
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(n)]
c = [ca[i][0] for i in range(n)]
a = [ca[i][1:] for i in range(n)]
ans = 0
cost = sum(c)
for i in range(2**n):
    kari = 0
    skill = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            kari += c[j] 
            skill = [x + y for (x,y) in zip(skill,a[j])]
            
    if all([z >= x for z in skill ]):
        cost= min(cost,kari)
        ans += 1
        
if ans == 0:
    print(-1)
else:
    print(cost)

Solution (Python):
N, M, X = map(int,input().split())
A = [[int(x) for x in input().split()] for _ in range(N)]
 
INF = float('inf')
ans = INF


for i in range(2**N):
    tmp = [0 for _ in range(M+1)]
    b = bin(i)[2:].zfill(N)
    
    
    for n in range(N):
        for m in range(M+1):
            tmp[m] += A[n][m] * int(b[N-1-n])
    
 
    if min(tmp[1:]) >= X:
        ans = min(ans, tmp[0])
 
if ans == INF:
    ans = -1
print(ans)

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

add = []

for i in range(2**n):
    skill = [0]*(m+1)
    for j in range(n):
        if ((i>>j) & 1):
            skill = list(map(sum, zip(skill, ca[j])))
    if min(skill[1:])>=x:
        add.append(skill)

if add:
    add.sort()
    print(add[0][0])
else:
    print(-1)

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

INF = float('inf')
ans = INF

for i in range(2**N):
    tmp = [0 for _ in range(M+1)]
    b = bin(i)[2:].zfill(N)
    
    for n in range(N):
        for m in range(M+1):
            tmp[m] += A[n][m] * int(b[N-1-n])

    if min(tmp[1:]) >= X:
        ans = min(ans, tmp[0])

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

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

INF = float('inf')
ans = INF

for i in range(2**N):
    tmp = [0 for _ in range(M+1)]
    b = bin(i)[2:].zfill(N)
    
    for n in range(N):
        for m in range(M+1):
            tmp[m] += A[n][m] * int(b[N-1-n])

    if min(tmp[1:]) >= X:
        ans = min(ans, tmp[0])

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

Solution (Python):
def check(learn_total):
    for i in range(m):
        if learn_total[i] < x:
            return False  
    return True 

def calc_price(bit):
    price_total = 0 
    learn_total = [0] * m 

    for i in range(n):
        if (bit >> i) & 1:  
            price_total += c[i]  
            learn = a[i]  
            for j, la in enumerate(learn): 
                learn_total[j] += la

   
    if check(learn_total):
        return price_total 
    else:
        return INF

if __name__ == '__main__':
    n, m, x = list(map(int, input().split()))

    
    c = []  
    a = []  

    for i in range(n):
        c_temp, *a_temp = list(map(int, input().split()))  
        c.append(c_temp)
        a.append(a_temp)

    INF = float("inf")
    ans = INF

    for bit in range(1 << n):
        price = calc_price(bit)  
        ans = min(ans, price)  

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

Solution (Python):
INF = float('inf')

def dfs(i, C):
    if i == N:
        if min(C[1:]) >= X:
            return C[0]
        else:
            return INF
    res = INF
    tmp = [0 for _ in range(M+1)]
    for bit in range(2):
        for j in range(M+1):
            tmp[j] = C[j] + A[i][j] * bit
        res = min(res, dfs(i+1, tmp))
    return res

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

ans = dfs(0, [0 for _ in range(M+1)])
if ans == INF:
    ans = -1
print(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:])
ans = -1
for i in range(1 << N): 
    experience = [0] * M
    cost = 0
    
    for j in range(N):
        if (i >> j) & 1 == 0: 
            continue 
        cost += C[j] 
        for k in range(M):   
            experience[k] += A[j][k]
        if all(x >= X for x in experience): 
            if ans == -1:
                ans = cost
            else:
                ans = min(ans, cost) 
print(ans)

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

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

ans = 10**10

for i in range(2**N):
  cost = 0
  skills = [0] * M
  for j in range(N):
    if ((i >> j) & 1):
      
      for k in range(M):
        skills[k] += CA[j][1+k]
      cost += CA[j][0]
  
  if all([n >= X for n in skills]):
  	ans = min(ans, cost)
  
if ans == 10**10:
  print(-1)
else:
  print(ans)

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

for i in range(2**n):
  money=0
  tm=[0]*m
  for j in range(n):
    if (i>>j)&1==0:
      continue
    money+=c[j]
    for k in range(m):
      tm[k]+=a[j][k]
    if all(xx>=x for xx in tm):
      if result==-1:
        result=money
      else:
        result=min(money,result)
print(result)

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


N, M, X = list(map(int, input().split()))
INF = 10**5 * 12 + 1
books = np.array([list(map(int, input().split())) for i in range(N)])
ans = INF
for selection in product([0, 1], repeat=N):
    selection = np.array(selection).reshape(N, 1)
    res = (books * selection).sum(axis=0)
    if min(res[1:]) >= X:
        ans = min(ans, res[0])
print(ans if ans != INF else -1)

Solution (Python):
n,m,x = map(int,input().split())
l = []
for i in range(n):
    ca = list(map(int,input().split()))
    l.append(ca)
ans = 9999999999
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(l[j])
    skill = [0]*m
    enough = [0]*m
    money = 0
    for sub in bag:
        money += sub[0]
        for k in range(1,m+1):
            skill[k-1] += sub[k]
            if skill[k-1]>=x:
                enough[k-1] += 1
        if 0 not in enough:
            if ans>money:
                ans = money
if ans == 9999999999:
    
    print(-1)
else:
    print(ans)

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


def list_add(l):
    wrk = np.array(l[0], dtype=int)
    for i in l[1:]:
        wrk = np.array(wrk, dtype=int) + np.array(i, dtype=int)
    return wrk.tolist()


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

ans = -1

for i in range(1, n+1):
    c_list = list(itertools.combinations(l, i))
    for c in c_list:
        t = list_add(c)
        ok = True
        for c in t[1:]:
            if c < x:
                ok = False
        if ok:
            if ans == -1 or ans > t[0]:
                ans = t[0]
print(ans)

Solution (Python):
import itertools
def main():
    n,m,x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    ans = 10**9

    for i in range(2**n):
        bit = format(i, f'0={n}b')
        rikaido = [0]*m
        kingaku = 0
        for num, val in enumerate(bit):
            if val == '1':
                kingaku += c[num][0]
                for num2, val2 in enumerate(c[num][1:]): rikaido[num2] += val2
        if min(rikaido) >= x:
            ans = min(kingaku, ans)

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
readline = sys.stdin.readline

N,M,X = map(int,readline().split())
books = [None] * N
for i in range(N):
  data = list(map(int,readline().split()))
  cost = data[0]
  point = data[1:]
  books[i] = [cost,point]
  

INF = 10 ** 10
ans = INF
import itertools
for i in range(1, N + 1):
  for target in itertools.combinations(books, i):
    skills = [0] * M
    totalcost = 0
    for t in target:
      totalcost += t[0]
      point = t[1]
      for j in range(len(point)):
        skills[j] += point[j]
    if totalcost < ans:
      for j in range(len(skills)):
        if skills[j] < X:
          break
      else:
        ans = totalcost
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):
import itertools


def bit(n, m):
  bit_list = list(itertools.product([i for i in range(m)], repeat=n))
  return bit_list

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

ans = 10 ** 10
bits = bit(N, 2)
for bit_ptr in  bits:
  und_algo = [0 for _ in range(M)]
  tmp = 0
  for i in range(N):
    if bit_ptr[i] == 1:
      for j in range(M):
        und_algo[j] += A[i][j+1]

      tmp += A[i][0]
  
  flag = True
  for i in range(M):
    if und_algo[i] < X:
      flag = False

  if flag:
    ans = min(ans, tmp)

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

Solution (Python):
import itertools
def main():
    n,m,x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    
    ans = 10**9
    possible = False

    for i in range(1, n+1):
        for j in itertools.combinations(c,i):
            rikaido = [0]*m
            kingaku = 0
            for k in j:
                kingaku += k[0]
                for num, val in enumerate(k[1:]):
                    rikaido[num] += val

            if min(rikaido) >= x:
                ans = min(ans, kingaku)
    print(-1) if ans == 10**9 else print(ans)

if __name__ == "__main__":
    main()

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

me = [x] * m
min = sum(c)+1
cost = 0

def f(me, books, ctbl, cost):
    global min 
    if len(books) == 0:
        return
    for i,b in enumerate(books):
        t = tuple(map(lambda x:x[0]-x[1], zip(me, b)))
        if len(tuple(filter(lambda x:x>0, t))) > 0:
            f(t, books[i+1:], ctbl[i+1:], cost+ctbl[i])
        else:
            if min > cost+ctbl[i]:
                min = cost+ctbl[i]
    f(me, books[1:], ctbl[1:], cost)

f(me, a, c, 0)
if sum(c) < min:
    print(-1)
else:
    print(min)

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

a = [input().split() for i in range(n)]
c = [a[i].pop(0) for i in range(n)]

INF = 1001001001
ans = INF
for s in range(1<<n):
    cost = 0
    d = [0]*m
    for i in range(n):
        if s>>i & 1:
            cost += int(c[i])
            for j in range(m):
                d[j] += int(a[i][j])
    ok = True
    for j in range(m):
        if d[j] < x:
            ok = False
    if ok:
        ans = min(ans,cost)

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

Solution (Python):
import numpy
import sys

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

row_sum = numpy.sum(book, axis=0)
if(min(row_sum)<X):
  print("-1")
  sys.exit()

result=-1
for i in range(2**N):
  t=[0]*M
  money=0
  for j in range(N):
    
    if (i>>j)&1==0:
      continue
    money+=book[j][0]
    for k in range(1,M+1):
      t[k-1]+=book[j][k]
  
  if all(xx>=X for xx in t):
    if(result==-1):
      result=money
    else:
      result=min(result,money)
print(result)

Solution (Python):
N, M, X = map(int, input().split())
C = [0]*N
A = [[0]*(M+1)]*N
cost = 1
for i in range(N):
  A[i] = list(map(int, input().split()))
  cost += A[i][0]
cost_temp = cost 
for i in range(2**N):
  flag = True
  B = [False]*N
  D = [0]*(M+1)
  for j in range(N):
    if ((i >> j) & 1):
      B[j]=True
  for n in range(N):
    if B[n]:
      for m in range(M+1):
        D[m] += A[n][m]
  for m in range(M):
    if D[m+1]<X:
      flag = False
      break
  if flag and cost > D[0]:
    cost = D[0]
if cost == cost_temp:
  print(-1)
else:
  print(cost)

Solution (Python):
n,m,x=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(n)]
result=-1
for i in range(2**n):
  t=[0]*m
  money=0
  for j in range(n):
    if (i>>j)&1==0:
      continue
    money+=c[j][0]
    for k in range(1,m+1):
      t[k-1]+=c[j][k]
  if all(xx>=x for xx in t):
    if result==-1:
      result=money
    else:
      result=min(result,money)
print(result)

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]
    for k in range(M):
      t[k]+=A[j][k]
    
  
  if all(x>=X for x in t):
    if result==-1:
      result=c
    else:
      result=min(result,c)

print(result)

Solution (Python):
n, m, x = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
C, A = list(map(lambda x: x[0], A)), list(map(lambda x: x[1:], A))
ans = 10**18
for i in range(2**n):
    M = [0]*m
    cost = 0
    for j in range(n):
        if (i>>j)&1:
            cost += C[j]
            for k in range(m):
                M[k] += A[j][k]
                
    
    if all([mm >= x for mm in M]): ans = min(ans, cost)
print(ans if ans!=10**18 else '-1')

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

ans = float('inf')

for i in range(1<<N):
  a = [0] * (M+1)

  for j in range(N):
    if ((i >> j) & 1):
      for x, k in enumerate(CA[j]):
        a[x] += k

  if all(a >= X for a in a[1:]):
    ans = min(ans, a[0])

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

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

c = [0 for _ in range(n)]
a = [[0] for j in range(n)]

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

cmin = sum(c) + 1
tassei = False

for i in range(1<<n):
  rikai = [0 for i in range(m)]
  cnow = 0
  for j in range(n):
    if i & (1<<j):
      cnow+=c[j]
      for mnow in range(m):
        rikai[mnow]+=a[j][mnow]
  if min(rikai)>=x:
    tassei = True
    cmin = min(cmin, cnow)

if tassei:
  print(cmin)
else:
  print(-1)

Solution (Python):
from itertools import combinations

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

ans = 10000000000

for i in range(1, n+1):
	for cb in list(combinations(rng,i)):
		r = [0]*m
		cout = 0
		for j in cb:
			cout+=c[j]
			for k in range(m):
				r[k]+=a[j][k]
		if min(r)>=x:
			ans = min(ans, cout)
		
print(ans if ans !=10000000000 else -1)

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

for j in range(n):
    c.append([int(i) for i in input().split()])
'''
und_list=[]
for i in range(n):
    for j in range(1,m+1):
        und_list[j-1] += c[i][j]
if min(und_list) < x:
    print(-1)
else:
'''
ans=-1
for i in range(2**n):
    und_list=[0]*m
    sum_money=0
    for j in range(n):
        if((i >> j)&1):
            for k in range(m):
                und_list[k] += c[j][k+1]
            sum_money+=c[j][0]
    if min(und_list)>=x:
        if ans==-1:
            ans= sum_money
        elif ans > sum_money:
            ans=sum_money
print(ans)

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

m = []
A = []
for x in range(N):
  A = list(map(int, input().split()))
  m.append(A)

ans = 1000000007
for i in range(2**N):
  l = []
  total = 0
  for j in range(N):
    if ((i >> j) & 1):
      l.append(m[j])
  a = [0] * (M+1)
  for x in l:
    for i, k in enumerate(x):
      a[i] += k

  found = True
  for i, x in enumerate(a):
    if i >= 1:
      if x < X:
        found = False

  if found:
    ans = min(ans, a[0])

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

Solution (Python):
from itertools import  product
N,M,X = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(N)]
for i in range(1,M+1):
    count=0
    for j in range(N):
        count+=ca[j][i]
    if count<X:
        print(-1)
        exit()

ans = []
for z in product((0, 1), repeat=N):
    count=0
    count2=[0]*M
    for i in range(N):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,M+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(M):
        if count2[i]<X:
            break
    else:
        ans.append(count)
print(min(ans))

Solution (Python):
from itertools import  product
N,M,X = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(N)]
for i in range(1,M+1):
    count=0
    for j in range(N):
        count+=ca[j][i]
    if count<X:
        print(-1)
        exit()

ans = 10**9
for z in product((0, 1), repeat=N):
    count=0
    count2=[0]*M
    for i in range(N):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,M+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(M):
        if count2[i]<X:
            break
    else:
        ans=min(count,ans)
print(ans)

Solution (Python):
import copy
s = input().split()

n = int(s[0])
m = int(s[1])
x = int(s[2])

s_list = [[0 for i in range(m+1)] for j in range(n)]

for i in range(n):
    r = input().split()
    s_list[i][0] = int(r[0])
    for j in range(1,m + 1):
        s_list[i][j] = int(r[j])


gen = [0] * (m + 1)
kakaku = -1

for i in range(2 ** n):
    kari = copy.copy(gen)
    for j in range(n):
        if ((i >> j) & 1):
            for l in range(m+1):
                kari[l] += s_list[j][l]

    check = 0
    for j in range(1,m + 1):
        if kari[j] < x:
            check = 1
            break
    if check == 0 and (kari[0] < kakaku or kakaku == -1):
        kakaku = kari[0]

print(kakaku)

Solution (Python):
n, m, x0 = list(map(int, input().split()))
c = [0] * n
a = [[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:]

b = [[0]*m for i in range(2**n)]
money = [0] * (2**n)

list2n = [list(f"{i:0{n}b}") for i in range(2**n)]

for i, x in enumerate(list2n):
    for j in range(n):
        money[i] += c[j] * int(x[j])
        for k in range(m):
            b[i][k] += a[j][k] * int(x[j])
            
ans = 1e10
for i in range(2**n):
    flag = True
    for j in range(m):
        if b[i][j] < x0:
            flag = False
            break
    if flag == True:
        ans = min(ans, money[i])

print(ans) if ans != 1e10 else print(-1)

Solution (Python):
n, m, x0 = list(map(int, input().split()))
c = [0] * n
a = [[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:]

b = [[0]*m for i in range(2**n)]
money = [0] * (2**n)

list2n = [list(f"{i:0{n}b}") for i in range(2**n)]

for i, x in enumerate(list2n):
    for j in range(n):
        money[i] += c[j] * int(x[j])
        for k in range(m):
            b[i][k] += a[j][k] * int(x[j])
            
ans = 1e10
for i in range(2**n):
    flag = True
    for j in range(m):
        if b[i][j] < x0:
            flag = False
            break
    if flag == True:
        ans = min(ans, money[i])

print(ans) if ans != 1e10 else print(-1)

Solution (Python):
import copy
s = input().split()

n = int(s[0])
m = int(s[1])
x = int(s[2])

s_list = [[0 for i in range(m+1)] for j in range(n)]

for i in range(n):
    r = input().split()
    s_list[i][0] = int(r[0])
    for j in range(1,m + 1):
        s_list[i][j] = int(r[j])


gen = [0] * (m + 1)
kakaku = -1

for i in range(2 ** n):
    k = i
    kari = copy.copy(gen)
    for j in reversed(range(n)):
        if k >= 2 ** j:
            k -= 2 ** j
            for l in range(m+1):
                kari[l] += s_list[j][l]

    check = 0
    for j in range(1,m + 1):
        if kari[j] < x:
            check = 1
            break
    if check == 0 and (kari[0] < kakaku or kakaku == -1):
        kakaku = kari[0]

print(kakaku)

Solution (Python):
import sys
input = sys.stdin.readline




'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

ans = []
mon = [0]*(2**n)

def ok(anss,x):
    for i in range(len(anss)):
        if anss[i]<x:
            return False
    return True

for i in range(2**n):
    
    
    anss=[0]*m
    for j in range(n):
        
        
        if ((i >> j) & 1):
            mon[i] += l[j][0]
            for k in range(1,m+1):
                anss[k-1]+=l[j][k]
    
    if ok(anss,x):
        
        ans.append(mon[i])

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

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

Solution (Python):
nmx=list(map(int, input().split()))
N=nmx[0]
M=nmx[1]
X=nmx[2]
ls=[input().split() for i in range(N)]
flg=False
alist=[[0 for p in range(M)] for q in range(2**N)]
clist=[0]*2**N 
for k in range(2**N):
    for i in range(N):
        if (k>>i) & 1:
            c=int(ls[i][0])
            clist[k]+=c
            for j in range(M):
                a=int(ls[i][j+1])
                alist[k][j]+=a
    if min(alist[k])<X:
        clist[k]=12*10**5+1
    else:
        flg=True
if flg:
    clist.sort()
    print(clist[0])
else:
    print('-1')

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

for i in range(len(AA)):
    C[i] = AA[i][0]
    A[i] = AA[i][1:]

ans = sum(C) + 1

for p in range(2 ** N):
    Y = [0] * M
    cnt = 0
    for i, c in enumerate(C):
        if p % 2 == 1:
            cnt += c
            for j, a in enumerate(A[i]):
                Y[j] += a
        p //= 2
        
        
    
    ans = min(ans, cnt) if min(Y) >= X else ans
print(ans if ans <= sum(C) else -1)

Solution (Python):
N, M, X = map(int, input().split())
C = [0] * N
A = [0] * N
AA = [list(map(int, input().split())) for i in range(N)]
for i in range(len(AA)):
    C[i] = AA[i][0]
    A[i] = AA[i][1:]
ans = sum(C) + 1
for p in range(2 ** N):
    Y = [0] * M
    cnt = 0
    for i, c in enumerate(C):
        if p % 2 == 1:
            cnt += c
            for j, a in enumerate(A[i]):
                Y[j] += a
        p //= 2
    ans = min(ans, cnt) if min(Y) >= X else ans
print(ans if ans <= sum(C) else -1)

Solution (Python):
INF = float("inf")

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

ans = INF
for i in range(2 ** N):
    B = [0] * M
    S = 0
    for j, (c, *a) in enumerate(A):
        if (i >> j) & 1:
            S += c
            for k, ak in enumerate(a):
                B[k] += ak
    if all(b >= X for b in B):
        ans = min(ans, S)

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

Solution (Python):
def solve(i, cost, know, x, a):
    global res
    if i == len(a):
        for j in range(m):
            if know[j] < x:
                return
        res = min(res, cost)
        return
    solve(i + 1, cost, know, x, a)
    for j in range(m):
        know[j] += a[i][j + 1]
    solve(i + 1, cost + a[i][0], know, x, a)
    for j in range(m):
        know[j] -= a[i][j + 1]
n, m, x = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(n)]
know = [0] * (m)
res = 10 ** 7
solve(0, 0, know, x, a)
print(res if res != 10 ** 7 else - 1)

Solution (Python):
nmx=list(map(int, input().split()))
N=nmx[0]
M=nmx[1]
X=nmx[2]
mylist=[]
for i in range(N):
    mylist.append(list(map(int, input().split())))
Ans=100000*12+1
for i in range(2**N):
    A=[0]*M
    C=0
    for j in range(N):
        if (i>>j) & 1:
            C+=mylist[j][0]
            for k in range(M):
                A[k]+=mylist[j][k+1]
    if min(A)>=X:
        Ans=min(Ans, C)
if Ans==100000*12+1:
    print(-1)
else:
    print(Ans)

Solution (Python):
nmx=list(map(int, input().split()))
N=nmx[0]
M=nmx[1]
X=nmx[2]
mylist=[]
for i in range(N):
    mylist.append(list(map(int, input().split())))
Ans=100000*12+1
for i in range(2**N):
    A=[0]*M
    C=0
    for j in range(N):
        if (i>>j) & 1:
            C=C+mylist[j][0]
            for k in range(M):
                A[k]=A[k]+mylist[j][k+1]
    if min(A)>=X:
        Ans=min(Ans, C)
if Ans==100000*12+1:
    print(-1)
else:
    print(Ans)

Solution (Python):
def main():
    n, m, x = map(int, input().split())
    ca = [list(map(int, input().split())) for _ in [0]*n]
    ans = 10**20
    for i in range(2**n):
        temp = [0]*m
        cost = 0
        for j in range(n):
            if i & 2**j:
                cost += ca[j][0]
                for k in range(m):
                    temp[k] += ca[j][k+1]
        for j in range(m):
            if temp[j] < x:
                break
        else:
            ans = min(ans, cost)
    if ans == 10**20:
        print(-1)
    else:
        print(ans)


main()

Solution (Python):
import itertools
import numpy as np

N, M, X = map(int, input().split())
C = []
H = []
for i in range(N):
    tmp = [int(x) for x in input().split()]
    H.append(tmp)



for i in range(2 ** N):
    cost = []
    for j in range(N):
        if bin(i).replace("0b", "").zfill(N)[j] == "1":
            cost.append(H[j])
            

    cost = np.array(cost)
    cost = cost.reshape(-1, M + 1)
    cost = np.sum(cost, axis=0)
    
    C.append(list(cost))


result = []
for i in C:
    flag = True
    for j in range(M):
        if i[j + 1] >= X and flag:
            flag = True
        else:
            flag = False
    if flag:
        result.append(i[0])

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

Solution (Python):
N, M, X = map(int, input().split())
C = []
lst = []

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

p = [i for i in range(N)]

cost = 10 ** 8
for i in range(2 ** N):
    bit = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            bit.append(p[j])

    t = [0] * M
    for m in range(M):
        c = 1
        for n in bit:
            t[m] += lst[n][m]
        if t[m] < X:
            c = 0
            break
    co1 = 0
    if c:
        for n in bit:
            co1 += C[n]
        if co1 <= cost:
            cost = co1

if cost ==  10 ** 8:
    cost = -1

print(cost)

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

N, M, X = list(map(int, input().split()))
INF = 10**5 * 12 + 1
books = np.array([list(map(int, input().split())) for i in range(N)])
ans = INF
for selection in product([0, 1], repeat=N):
    selection = np.array(selection).reshape(N, 1)
    res = (books * selection).sum(axis=0)
    if min(res[1:]) >= X:
        ans = min(ans, res[0])
print(ans if ans != INF else -1)

Solution (Python):
import sys
import numpy as np

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

N,M,X = map(int, readline().split())
data = np.array(read().split(), np.int64)
data = data.reshape(N,-1)
C = data[:,0]
A = data[:,1:]

cost = np.zeros(1<<N, np.int64)
ability = np.zeros((1<<N, M), np.int64)

for i in range(N):
  cost[1<<i:1<<(i+1)] = cost[:1<<i] + C[i]
  ability[1<<i:1<<(i+1)] = ability[:1<<i] + A[i]

ok = np.all(ability >= X, axis=1)

x = cost[ok]
answer = -1 if len(x) == 0 else x.min()
print(answer)

Solution (Python):
def dec_bin(num, n):
    ret = ""
    while num > 0:
        ret += str(num%2)
        num //= 2
    curr_len = len(ret)
    for i in range(0, n-curr_len):
        ret += '0'
    return ret[::-1]

min_cost = 100000000
nmx = [int(s) for s in input().split()]
n, m, x = nmx[0], nmx[1], nmx[2]
data = []
for i in range(n):
    row = [int(s) for s in input().split()]
    data.append(row)
for num in range(0, (1<<n)):
    dec = dec_bin(num, n)
    tot_cost = [0 for x in range(m)]
    price = 0
    for j in range(n):
        if dec[j] == '1':
            price += data[j][0]
            for i in range(m):
                tot_cost[i] += data[j][i+1]
    good = True
    for cost in tot_cost:
        if cost < x:
            good = False
            break
    
    if good:
        min_cost = min(price, min_cost)
if min_cost == 100000000:
    print(-1)
else:
    print(min_cost)