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):
import math
from sys import stdin,stdout

from heapq import heapify,heappop,heappush

from collections import Counter



    

def helper(bks,p,cc,alg,vis,m,n,x):
    
    if p==n:
        f=True
        for i in range(m):
            if alg[i]<x:
                f=False
                break
        if f:
            return cc
        return float('inf')    
    ans=float('inf')
    for b in range(p,n):
    
    
        for i in range(m):
            alg[i]+=bks[b][i+1]
        
        ans=min(ans,helper(bks,b+1,cc+bks[b][0],alg,vis,m,n,x) )
        
        for i in range(m):
            alg[i]-=bks[b][i+1]
    
    ans=min(ans,helper(bks,n,cc,alg,vis,m,n,x) )
    return ans


n,m,x=list(map(int,stdin.readline().split()))
bks=[[0]*(m+1) for _ in range(n)]

for i in range(n):
    bks[i]=list(map(int,stdin.readline().split()))
    

pos=True

alg=[0]*m
for i in range(n):
    for j in range(m):
        alg[j]+=bks[i][j+1]

for i in range(m):
    if alg[i]<x:
        pos=False
        break



if not pos:
    print(-1)
else:
    alg=[0]*m
    print(helper(bks,0,0,alg,set(),m,n,x))

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

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

matrix = np.zeros((N,M+1))
for i in range(N):
    matrix[i] = np.array([int(n) for n in input().split()])

total = np.sum(matrix[:,1:],axis=0)
if not all(i >= X for i in total):
    print(-1)
    sys.exit(0)

def checkthresh(A, thresh):
    return all(i >= thresh for i in A)

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

cost = N*10**5
for subset in powerset(range(N)):
    sum_subset = np.zeros((1,M+1))
    for i in subset:
        sum_subset += matrix[i,:]
    sum_subset = sum_subset[0]
    if checkthresh(sum_subset[1:], X):
        cost = min(cost, sum_subset[0])

print(int(cost))

Solution (Python):
import itertools
import math
import fractions
import functools

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

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


nums = []
for i in range(n):
    nums.append(i)

temp = []
for i in range(1, n+1):
    for v in itertools.combinations(nums, i):
        rikaido = [0] * (m+1)
        for j in range(len(v)):
            for k in range(m+1):
                rikaido[k] += a_do[v[j]][k]

        temp.append(rikaido)

minimum = 10**20
for i in range(len(temp)):
    ok = True
    for j in range(1, m+1):
        if temp[i][j] < x:
            ok = False
    if(ok):
        minimum = min(minimum, temp[i][0])

if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

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

n,m,x = (int(x) for x in input().split())
seq = []
for _ in range(n):
    seq.append([int(i) for i in input().split()])
ans = float('inf')
for i in xrange(2**n):
    cost = 0
    knowledge = [0 for _ in xrange(m)]
    for j, c in enumerate(bin(i)[2:], n-len(bin(i)[2:])):
        if c =='1':
            cost += seq[j][0]
            for k in xrange(m):
                knowledge[k] += seq[j][1+k]
    if all([val >= x for val in knowledge]):
        ans = min(cost, ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
import itertools
n,m,x=list(map(int,input().split()))
ans=10**18
A=[list(map(int,input().split())) for i in range(n)]
for i, _ in enumerate(A,1):
  for j in itertools.combinations(A,r=i):
    B=list(zip(*j))
    
    C=[0]*(m+1)
    for m in range(m+1):
      C[m]=sum(B[m])
    if len([i for i in C[1:] if i>=x ])==m:
      ans=min(ans,C[0])
print(ans) if ans!=10**18 else print(-1)

Solution (Python):
import numpy as np  
import itertools

val = input()
val = val.split(" ")
val = [int(i) for i in val]  

I = np.zeros((val[0], val[1]+1))

for i in range(val[0]):
    val2 = input()
    val2 = val2.split(" ")
    val2 = [int(i) for i in val2]  
    I[i] = val2

seq = [i for i in range(val[0])]  


ans = []

for i in range(val[0]):
    Comb = list(itertools.combinations(seq, i+1))
    
    for j in Comb:
        Com_list = list(j)
        
        I_sum = [[I[k][l+1] for k in Com_list] for l in range(val[1])]
        
        I_sum_over_x = [sum(m) for m in I_sum if sum(m) >= val[2]]
        
        if(len(I_sum_over_x) == val[1]):
            
            I_sum2 = [I[n][0] for n in list(j)]
            
            
            ans.append(sum(I_sum2))


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

Solution (Python):
import numpy as np

max_n = 12
max_m = 12
def main():
    nmx = list(map(int, input().split()))
    c = [None]*nmx[0]
    a = [None]*nmx[0]
    for i in range(nmx[0]):
        ca = list(map(int, input().split()))
        c[i] = ca[0]
        a[i] = ca[1:]

    ms = -1
    
    


    
    
    
    
    

    
    poo = []
    for i in range(nmx[0]):
        poo.append([i])
        df(nmx[0], [i], poo)
    
    for i in poo:
        score = np.zeros([nmx[1]])
        p = 0
        for j in i:
            score += np.array(a[j])
            p += c[j]
        
        if all(score >= nmx[2]) and (ms > p or ms < 0):
            ms = p

    
    print(ms)

def df(n, m, store):
    
    for i in range(m[-1], n-1):
        tmp = list(m)
        tmp.append(i+1)
        store.append(tmp)
        df(n, tmp, store)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import math
import fractions
import functools

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

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


nums = []
for i in range(n):
    nums.append(i)
minimum = 10**20

temp = []
for i in range(1, n+1):
    for v in itertools.combinations(nums, i): 
        rikaido = [0] * (m+1)
        for j in range(len(v)):
            for k in range(m+1):
                rikaido[k] += a_do[v[j]][k]

        ok = True
        for j in range(1, m+1):
            if rikaido[j] < x:
                ok = False
        if(ok):
            minimum = min(minimum, rikaido[0])










if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

Solution (Python):
import numpy as np
INF = 10**9

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 = INF

for s in range(1 << N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if s >> i & 1:
            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 == INF:
    print(-1)
else:
    print(min_price)

Solution (Python):
n,m,x = (int(x) for x in input().split())
C = []
A = []
for i in range(n):
    list = [int(i) for i in input().split()]
    C.append(list[0])
    A.append(list[1:])
i = 0
case = [0]*(2**n)
chk = []
for i in range(2**n):
    chk.append([0]*m)
i = 0
for i in range(2 ** n):
    for j in range(n):
        if ((i >> j) & 1):
            case[i] += C[j]
            for l in range(m):
                chk[i][l] += A[j][l]
i = 0
j = 0
ans = []
flag = [True]*(2**n)
for i in range(2**n):
    for j in range(m):
        if chk[i][j]<x:
            flag[i] = False
    if flag[i]:
        ans.append(case[i])

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

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

from itertools import product

n, m, x = map(int, readline().split())
ca = [list(map(int, readline().split())) for _ in range(n)]
ans = float('inf')
for bit in product([0, 1], repeat=n):
    cnt = 0
    memo = [0] * m
    for i in range(n):
        if bit[i] == 1:
            cnt += ca[i][0]
            for j in range(m):
                memo[j] += ca[i][j + 1]
    for j in range(m):
        if memo[j] < x:
            break
    else:
        ans = min(ans, cnt)
if ans == float('inf'):
    ans = -1
print(ans)

Solution (Python):
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n,m,x = MI()
a = []
c = []
for i in range(n):
  dd = LI()
  c.append(dd[0])
  dd = dd[1:]
  a.append(dd)


INF = 1e14
ans = INF
for iters in range(1,n+1):
  xx = list(itertools.combinations(range(n), iters))
  for u in xx:
    bad = False
    score = [0] * m
    money = 0
    for i in u:
      money += c[i]
      for j in range(m):
        score[j] += a[i][j]

    for j in range(m):
      if score[j] < x:
        bad = True
        break
    
    if not bad:
      ans = min(money, ans)

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

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

nums = [0,1]
bools = np.array(list(itertools.product(nums, repeat=N)))
ans = 10000000
for i in range(len(bools)):
    sumCA = sum(bools[i].reshape((N,1))*CA)
    flag = 1
    for j in range(1,M+1):
        if sumCA[j] < X:
            flag = 0
    if flag and sumCA[0] < ans:
        ans = sumCA[0]
        
if ans == 10000000:
    print(-1)
else:
    print(int(ans))

Solution (Python):
import copy
 
def dfs(A, times):
    if times == N:
        if min(A[1:M+1]) >= X:
            ans[0] = min(A[0], ans[0])
        return
    dfs(copy.copy(A), times+1)
    for i in range(M+1):
        A[i] = A[i] + L[times][i]
    dfs(copy.copy(A), times+1)

N, M, X = map(int, input().split())
L = [0] * (N)
for i in range(N):
    L[i] = [int(x) for x in input().split()]

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

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






















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

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

INF = float('INF')
min_cost = INF

def dfs(i, cost, learn):
    if i == N:
        if min(learn) >= X: 
            return cost
        else:
            return INF

    else:
        new_learn = [(x+y) for (x, y) in zip(A[i], learn)]
        cost = min(dfs(i+1, cost, learn), dfs(i+1, cost + C[i], new_learn))
        return cost

min_cost = dfs(0, 0, [0] * M)

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

Solution (Python):
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 s in range(1 << N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if s >> i & 1:
            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):
from itertools import product

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

bit = [0, 1]
ans = float('inf')
for l in product(bit, repeat=n):
    a = [0] * m
    cnt = 0
    for i, buy in enumerate(l):
        if buy == 1:
            cnt += ca[i][0]
            for j in range(1, m + 1):
                a[j - 1] += ca[i][j]
    if all(i >= x for i in a):
        ans = min(ans, cnt)

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

Solution (Python):
import sys
n,m,x= map(int, sys.stdin.readline().rstrip("\n").split())
lines = [ [int(s) for s in line.split()] for line in sys.stdin ]

books = {}
num = 0
for a in range(2):
    for b in range(2):
        for c in range(2):
            for d in range(2):
                for e in range(2):
                    for f in range(2):
                        for g in range(2):
                            for h in range(2):
                                for i in range(2):
                                    for j in range(2):
                                        for k in range(2):
                                            for l in range(2):
                                                for o in range(2):
                                                    books[num] = [a,b,c,d,e,f,g,h,i,j,k,l]
                                                    num += 1
price = -1
skill = {}
for i in range(2**13-1):
    price_ = 0
    for j in range (m):
        skill[j] = 0
    for j in range(n):
        if books[i][j] == 1:
            price_  += lines[j][0]
            for k in range(m):
                skill[k] = skill[k] + lines[j][k+1]
        for k in range(m):
            if skill[k] < x:
                break
        else:
            if price == -1:
                price = price_
            else:
                price = min(price, price_)
print(price)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import copy
 
def dfs(A, times):
    if times == N:
        if min(A[1:M+1]) >= X:
            ans[0] = min(A[0], ans[0])
        return
    dfs(copy.copy(A), times+1)
    for i in range(M+1):
        A[i] = A[i] + L[times][i]
    dfs(copy.copy(A), times+1)

N, M, X = map(int, input().split())
L = [0] * (N)
for i in range(N):
    L[i] = [int(x) for x in input().split()]

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

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

N,M,X=map(int, input().split())
list_=[list(map(int, input().split())) for _ in range(N)]
cost=100000001
list_C=[]

for i in range(N):
	list_C=np.array(list(combinations(list_,N-i)))
	count=0
	
	for h in range(len(list_C)):
		if all(np.sum(list_C[h], axis=0)[1:]>=X):
			if np.sum(list_C[h], axis=0)[0]<cost:
				cost=np.sum(list_C[h], axis=0)[0]
			
			count+=1
	if count==0:
		break

print(cost if cost<100000001 else "-1")

Solution (Python):
import numpy as np
N,M,X = map(int,input().split())
CA = [np.array(list(map(int,input().split()))) for i in range(N)]
ans = -1
for i in range(1,2**N):
    und = np.zeros(M+1,dtype=int)
    flag = True
    for j in range(N):
        if (i >> j) & 1:
            und += CA[j]
    for k in range(M):
        if und[k+1] < X:
            flag = False
            break
    if flag:
        tmp = und[0]
        if ans == -1:
            ans = tmp
        else:
            ans = min(ans,tmp)
print(ans)

Solution (Python):
import sys 
input = sys.stdin.readline
def dp(start,algo,cost):
	if start>n:
		return
	global ans
	if all([True if i>=x else False for i in algo ]):
		ans = min(ans, cost)

	for i in range(start,n):
		temp = list(algo)
		for j in range(1,m+1):
			temp[j-1] += arr[i][j]
		dp(i+1, temp, cost+arr[i][0])

for tt in range(1):
	n,m,x = map(int,input().split())
	arr = []
	cost = [0]*m
	ans = float('inf')
	for i in range(n):
		l = list(map(int,input().split()))
		arr.append(l)
	dp(0,cost,0)
	if ans != float('inf'):
		print(ans)
	else:
		print(-1)

Solution (Python):
import numpy as np

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

min_cost = 10 ** 9
for bit in range(1, 1 << n):
  purchase = np.zeros(m + 1, dtype=int)
  for i in range(n):
    if bit & 1:
      purchase += books[i]
    bit >>= 1
  if np.all(purchase[1:] >= x):
    min_cost = min(min_cost, purchase[0])
if min_cost == 10 ** 9:
  print(-1)
else:
  print(min_cost)

Solution (Python):
import itertools

num_book, num_algo, target_score = map(int, input().split())

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

all_comb_book_info_list = []
for n in range(1, len(book_info_list) + 1):
    for conb in itertools.combinations(book_info_list, n):
        all_comb_book_info_list.append(list(conb))

price = -1
for comb_book_info_list in all_comb_book_info_list:
    book_info_total = [0] * (num_algo + 1) 
    for book_info in comb_book_info_list:
        book_info_total = [x + y for (x, y) in zip(book_info_total, book_info)]
    is_score_satisfied = True
    for total_score in book_info_total[1:]:
        if total_score < target_score:
            is_score_satisfied = False
        if not is_score_satisfied:
            break
    if not is_score_satisfied:
        continue
    if price == -1 or book_info_total[0] < price:
        price = book_info_total[0]

print(price)

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

master = [0 for i in range(M)]
bought = [False for i in range(N)]
cost = 0

def f(master, book):
    for i in range(M):
        master[i] += book[i]
    return master

for i in range(N):
    c, *a = list(map(int, input().split()))
    C.append(c)
    A.append(a)

m = 10**100
for i in range(2**N):
    cost = 0
    master = [0 for i in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            master = f(master, A[j])
    if min(master) >= X:
        m = min(m, cost)
    if i == 2**N-1 and min(master) < X:
        m = -1
        
print(m)

Solution (Python):
import itertools
import math
import fractions
import functools

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

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






















minimum = 10**20

nums = []
for i in range(n):
    nums.append(i)

temp = []
for i in range(1, n+1):
    for v in itertools.combinations(nums, i):
        cost = 0
        rikaido = [0] * (m)
        for j in range(len(v)):
            cost += c[v[j]]
            for k in range(m):
                rikaido[k] += a_do[v[j]][k]

        ok = True
        for k in range(m):
            if rikaido[k] < x:
                ok = False

        if(ok):
            minimum = min(minimum, cost)











if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

Solution (Python):
n,m,x=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
ans=10**10
for i in range(1<<n):
    a=[0]*m
    res=0
    for j in range(n):
        if i>>j&1:
            res+=c[j][0]
            for k in range(m):
                a[k]+=c[j][k+1]
    f=1
    for i in a:
        if i<x:
            f=0
            break
    if f:
        ans=min(ans,res)
print(ans if ans<10**10 else -1)

Solution (Python):
import itertools
n,m,x = map(int, input().split())
book = []
for i in range(n):
  b = list(map(int, input().split()))
  book.append(b)
book = sorted(book, key=lambda x:x[0])
junretu = itertools.permutations(range(n))
max_ = 2**n
min_nedan = 10**9
for j in range(max_):
  bit = format(j, "0"+str(n)+"b")
  count_list = [0]*m
  nedan = 0
  for b in range(n):
    if bit[b] == "1":
      naiyou = book[b]
      nedan += naiyou[0]
      for i in range(1, m+1):
        count_list[i-1] += naiyou[i]
  if min(count_list)>=x:
    if nedan < min_nedan:
      min_nedan = nedan
if min_nedan == 10**9:
  print(-1)
else:
  print(min_nedan)

Solution (Python):
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 1e18
for i in range(1 << n):
    b = [0] * m
    c = 0
    for j in range(n):
        if i & (1 << j):
            c += a[j][0]
            for k in range(m): b[k] += a[j][k + 1]
    for j in range(m):
        if b[j] < x: c = 1e18
    ans = min(ans, c)
print(-1 if ans == 1e18 else ans)

Solution (Python):
def dfs(pos):
    global N,M,X,a,CA,ans
    if pos==N:
        res = 0
        comp = [0] * M
        for i in range(N):
            if a[i]:
                res += CA[i][0]
                for j in range(1,M+1):
                    comp[j-1] += CA[i][j]
        for i in range(M):
            if comp[i]<X:
                return
        ans = min(ans,res)
        return
    a[pos] = 0
    dfs(pos+1)
    a[pos] = 1
    dfs(pos+1)

N,M,X = map(int,input().split())
CA = []
for i in range(N):
    CA.append(list(map(int,input().split())))
ans = int(1e9)
a = [0] * N
dfs(0)
if ans==int(1e9):
    print(-1)
else:
    print(ans)

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

INF=float("INF")
min_cost=INF

def dfs(i,cost,learn):
    if i==N:
        if min(learn)>=X:
            return cost
        else:
            return INF
    else:
        new_learn=[x+y for (x,y) in zip(A[i],learn)]

        
        cost=min(dfs(i+1,cost,learn),dfs(i+1,cost+C[i],new_learn))
        return cost

min_cost=dfs(0,0,[0]*M)

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

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

def main():
    N,M,X=map(int,input().split())
    ans=INF
    CA=[[int(_) for _ in input().split()] for _ in range(N)]
    for bit in range(2**N):
        money=0
        tmp=[0]*M
        for i in range(N):
            if (bit >> i) & 1:
                money += CA[i][0]
                for j in range(1, M+1):
                    tmp[j-1] += CA[i][j]
        if min(tmp) >= X:
            ans=min(ans, money)
    print(-1 if ans == INF else ans)

main()

Solution (Python):
import itertools
import math
import fractions
import functools

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

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


minimum = 10**20
for pat in range(0, (1<<n)): 
    cost = 0
    rikaido = [0] * m
    for i in range(n):
        if((pat >> i) & 1): 
            cost += c[i]
            for k in range(m):
                rikaido[k] += a_do[i][k]
    ok = True
    for k in range(m):
        if(rikaido[k] < x):
            ok = False
    if(ok):
        minimum = min(minimum, cost)

if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

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

INF=float("INF")
min_cost=INF

def dfs(i,cost,learn):
    if i==N:
        if min(learn)>=X:
            return cost
        else:
            return INF
    else:
        new_learn=[x+y for (x,y) in zip(A[i],learn)]
        cost=min(dfs(i+1,cost,learn),dfs(i+1,cost+C[i],new_learn))
        return cost

min_cost=dfs(0,0,[0]*M)

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

Solution (Python):
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
    li=list(map(int,input().split()))
    C.append(li[0])
    A.append(li[1:])
ans=10**20
for i in range(2**N):
    li=[0]*M
    cost=0
    for j in range(N):
        if(i>>j&1):
            cost+=C[j]
            for k in range(M):
                li[k]+=A[j][k]
    ok=True
    for j in range(M):
        if(li[j]<X):
            ok=False
            break
    if ok:
        ans=min(ans,cost)
print(ans if ans!=10**20 else -1)

Solution (Python):
import sys

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

n, m, x = map(int, readline().split())
ca = list(map(int, read().split()))

flg = 0
c_min = 1000000000

for i in range(1, 2**n + 1):
    sum_a = [0] * (m+1)
    check = 0
    
    s = bin(i)[2:].zfill(n)
    for j in range(n):
        if s[j] == "1":
            sum_a = [x + y for x, y in zip(sum_a, ca[(m+1)*j:(m+1)*(j+1)])]

    
    for k in range(1, m+1):
        if sum_a[k] >= x:
            check += 1
        if check == m:
            c_temp = sum_a[0]
            flg = 1
            if c_temp < c_min:
                c_min = c_temp

if flg == 1:
    print(c_min)
else:
    print("-1")

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

def makeTableA(dat,n,m):
    tbl=[[0]*m]*n
    
    for i in range(n):
        tup=dat[i]
        a=tup[1]
        
        
        
        tbl[i]=list(a) 
        
    return tbl  

def main(n,m,x,dat):
    tblA=makeTableA(dat,n,m)
    
    tblB=[[0]*(m+2)]*2**n  
    
    for i in range(2**n):
        tblB[i]=[0]*(m+2)
        b=1
        for j in range(n):
            if(i&b==b):
                for k in range(m):
                    
                    tblB[i][k]+=tblA[j][k]
                    
                tblB[i][m]+=dat[j][0]
                
            b=b*2
        tblB[i][m+1]=min(tblB[i][0:m])
        
    
    
    Pmin=12*10**5+1
    for i in range(2**n):
        if(tblB[i][m+1]>=x):
            price=tblB[i][m]
            if(price < Pmin):
                Pmin=price
    if(Pmin==12*10**5+1):
        Pmin=-1
    return Pmin


if __name__=='__main__':
    n,m,x,dat=readinput()
    ans=main(n,m,x,dat)
    print(ans)

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

ans = 100000 * n + 1

for bit in range(1 << n):
    A = [0] * m
    csum = 0

    for i in range(n):
        if bit & (1 << i):
            for j in range(m):
                A[j] += a[i][j]
            csum += c[i]

    if min(A) >= x:
        ans = min(ans, csum)

print((ans if ans != 100000 * n + 1 else -1))

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

for i in range(n):
    a=list(map(int,input().split()))
    l.append(a)
ans=99999999
for i in range(2 ** n):
    bag = []
    for j in range(n):  
        if ((i >> j) & 1): 
            bag.append(l[j])  
    skill=[0]*m
    enou=[0]*m
    mone=0
    for sub in bag:
        mone+=sub[0]
        for kk in range(1,m+1):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enou[kk-1]+=1
    if 0 not in enou:
        if ans>mone:
            ans=mone
if ans==99999999:
    print(-1)
else:
    print(ans)

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

ans = 10**9
for i in range(2**n):
  cost = 0
  point = [0]*m
  for j in range(n):
    if (i>>j)&1:
      cost += books[j][0]
      for k in range(1, m+1):
        point[k-1] += books[j][k]
  flag = True
  for j in range(m):
    if point[j] < x:
      flag = False
  if flag and ans > cost:
    ans = cost

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

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

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


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


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

    min_price = INF
    for r in range(1, N + 1):
        for comb in combinations(range(N), r):
            skills = [sum(A[i][j] for i in comb) for j in range(M)]
            if all(s >= X for s in skills):
                total_price = sum(c for i, c in enumerate(C) if i in comb)
                if min_price > total_price:
                    min_price = total_price

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

    return


if __name__ == '__main__':
    main()

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

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

kingakumin = 10000000000

for i in range(2 ** n):
    now = []
    inow = i
    for j in range(n):
        now.append(i % 2)
        i = i // 2

    syuutoku = []
    for j in range(m):
        syuutoku.append(0)

    kingaku = 0
    for j in range(n):
        if now[j] == 1:
            kingaku = kingaku + cas[j][0]
            for k in range(m):
                syuutoku[k] = syuutoku[k] + cas[j][k + 1]

    flag = True
    for j in range(m):
        if syuutoku[j] < x:
            flag = False

    if flag and kingakumin > kingaku:
        kingakumin = kingaku

if kingakumin == 10000000000:
    kingakumin = -1

print(kingakumin)

Solution (Python):


n,m,x=map(int,input().split())
from itertools import combinations
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
l1=[]
for i in range(n):
    l1.append(i)
l2=[]
for i in range(1,n+1):
    lx=[0]*i
    lyy=[0]*m
    for lx in combinations(l1,i):
        ly=lyy.copy()
        a=0
        for p in range(1,m+1):
            for k in lx:
                ly[p-1]+=l[k][p]
        for k in lx:
            a+=l[k][0]
        for j in ly:
            if j<x:
                a=0
                break
        if a!=0:
            l2.append(a)
if len(l2)!=0:
    print(min(l2))
else:
    print(-1)

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

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

row = [i for i in range(1, N+1)]
ans = float("INF")
for i in range(1, N+1):
  for v in combinations(row, i):
    q = deque(v)
    cost = 0
    Asum = [0]*M
    while q:
      a = q.popleft() - 1
      cost += CA[a][0]
      for j in range(M):
        Asum[j] += CA[a][j+1]
    flag = True
    for m in range(M):
      if Asum[m] < X:
        flag = False
    if flag:
      ans = min(ans, cost)
if ans == float("INF"):
  print(-1)
else:
  print(ans)