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):
def count_score(v):
    score = [0] * m
    for j in range(m):
        t = 0
        for i in range(n):
            t += a[i][j] * v[i]
        score[j] = t
    return score


def count_money(v):
    money = 0
    for i in range(n):
        money += c[i] * v[i]
    return money


def judge_understanding(score):
    ans = True
    for j in range(m):
        if score[j] < x:
            ans = False
            break
    return ans


def pu(j, in_vec, max_money):
    if j == n - 1:
        vec0 = in_vec
        vec0[n - 1] = 0
        score0 = count_score(vec0)
        money0 = count_money(vec0)
        understanding0 = judge_understanding(score0)

        vec1 = in_vec
        vec1[n - 1] = 1
        score1 = count_score(vec1)
        money1 = count_money(vec1)
        understanding1 = judge_understanding(score1)

        if understanding0:
            ans_vec = vec0
            ans_money = money0
        elif understanding1:
            ans_vec = vec1
            ans_money = money1
        else:
            ans_vec = in_vec
            ans_money = max_money
        
        return ans_vec, ans_money

    else:
        vec0 = in_vec
        vec0[j] = 0
        ans_vec0, ans_money0 = pu(j + 1, vec0, max_money)
        
        vec1 = in_vec
        vec1[j] = 1
        ans_vec1, ans_money1 = pu(j + 1, vec1, max_money)

        if ans_money0 <= ans_money1:
            ans_money = ans_money0
            ans_vec = ans_vec0
        else:
            ans_money = ans_money1
            ans_vec = ans_vec1

        return ans_vec, ans_money


if __name__ == "__main__":
    n, m, x = map(int, input().split())    
    c = [0] * n
    a = [[0] * m] * n

    for i in range(n):
        l = [int(x) for x in input().split()]
        c[i] = l[0]
        a[i] = l[1:m + 1]


    v = [0] * n

    mm = 1
    for i in range(n):
        mm += c[i]

    ans_vec, ans_money = pu(0, v, mm)

    if mm == ans_money:
        print(-1)
    else:
        print(ans_money)

Solution (Python):
import itertools
import numpy as np

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

num = [i for i in range(n)]

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


correct = []
for k in range(1, n+1):

  for v in itertools.combinations(num, k):
    test = [] 
    for j in v:
      test.append(book_list[j])
      sum_test = np.sum(test, axis = 0) 
      cnt = 0
      for i in range(1, m+1):
        if sum_test[i] >= x:
          cnt += 1
      if cnt == m:
        correct.append(sum_test[0]) 
        
if sum(correct) > 0:
  print(min(correct))
    
else:
  print('-1')

Solution (Python):


n, m, x = map(int, input().split())
c_list = []
a_list = []
for i in range(0, n):
    y_list = list(map(int, input().split()))
    c_list.append(y_list[0])
    a_list.append(y_list[1:])
ans = []
for i in range(0, 2**n):
    cost = 0
    gaku = [0] * m
    for j in range(0, n):
        if ((i >> j) & 1):
            cost += c_list[j]
            for k in range(0, m):
                gaku[k] += a_list[j][k]
    if all([r >= x for r in gaku]):
        ans.append(cost)
if ans:
    print(min(ans))
else:
    print(-1)

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


import itertools
M = 100000000000
ans = 0

for i in itertools.product([0, 1], repeat=n):
    dp = [0]*m
    tm= 0 
    for I in range(n):
        if i[I] == 1:
            for j in range(m):
                dp[j] += L[I][j]
            tm += C[I]* i[I]
    if all(dp[t]>=x for t in range(m)):
        M = min(M,tm)
if M==100000000000:
    print(-1)
else:
    print(M)

Solution (Python):
def resolve():
    import itertools
    impossible = 10 ** 20
    n, m, x = map(int, input().split())
    ans = impossible
    books = [None] * n
    for i in range(n):
        books[i] = list(map(int, input().split()))
    for i in itertools.product([True, False], repeat=n):
        u = [0] * m
        yen = 0
        for index, j in enumerate(i):
            if not j:
                continue
            yen += books[index][0]
            for k in range(m):
                u[k] += books[index][k + 1]
        for j in u:
            if j < x:
                break
        else:
            ans = min(yen, ans)
    print(ans if ans < impossible else -1)


if __name__ == '__main__':
    resolve()

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

cost = 100000000000000000000000
l = list(range(1,N+1))
import itertools
for i in range(1,N+1):
    check_l = list(itertools.combinations(l,i))
    for a in check_l:
        sub_list = [0] * (M + 1)
        for j in range(i):
            for k in range(M+1):
                sub_list[k] += C[a[j]-1][k]
        flag = True
        for p in range(M):
            if sub_list[p+1] < X:
                flag = False
        if flag == True:
            if cost > sub_list[0]:
                cost = sub_list[0]

if cost == 100000000000000000000000:
    print(-1)
else:
    print(cost)

Solution (Python):
import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict
from itertools import combinations as cmb

def check(s: list):
    if min(s) < X:
        return False
    return True

N, M, X = map(int, input().split())
G = [tuple(map(int, input().split())) for _ in range(N)]
s = [0 for i in range(M)]

res = 10 ** 15
ok = False
for i in range(1, N + 1):
    for cm in cmb(range(0, N), i):
        cnt = 0
        s = [0 for i in range(M)]
        for c in cm:
            cnt += G[c][0]
            for j in range(M):
                s[j] += G[c][j + 1]
        if check(s):
            res = min(cnt, res)
            ok = True

if ok:
    print(res)
else:
    print(-1)

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

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

cmin = 10**8
csum = 0
asum = [0 for i in range(m)]
for i in range(2**n):
    csum = 0
    for k in range(m):
        asum[k] = 0
    for j in range(n):
        if (i>>j)&1:
            csum+=c[j]
            for k in range(m):
                asum[k] += a[j][k]
    b = True
    for k in range(m):
        if asum[k]<x:
            b = False
            break
    if b:
        cmin = min(cmin,csum)

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

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


for Books in range(N):
    B_list.append(list(map(int, input().split(" "))))


bug = []
for k in range(M + 1):
    bug.append(0)

ways = []

for way in range(2**N):
    for book in range(N):
        if ((way >> book) & 1) == 1:
            for i in range(M + 1):
                bug[i] += B_list[book][i]

    
    O = bug.pop(0)
    clear = [l for l in bug if l >= X]
    

    if len(bug) == len(clear):
        ways.append(O)

    bug = []
    for k in range(M + 1):
        bug.append(0)

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

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

res = []
for i in range(1, len(num)+1):
    for conb in itertools.combinations(num, i):
        res.append(list(conb))
mini = float('inf')
for i in range(len(res)):
    tmp2 = [0] * (m+1)
    f = True
    for j in range(len(res[i])):
        for k in range(m+1):
            tmp2[k] += res[i][j][k]
    
    for l in range(len(tmp2)-1):
        if tmp2[l+1] < x:
            f = False
    if f == True and mini > tmp2[0]:
        mini = tmp2[0]

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

Solution (Python):
n, m, X = map(int, input().split())
 
ans = 10**9
 
price = []
a = []
for _ in range(n):
    c = [int(x) for x in input().split()]
    price.append(c[0])
    a.append(c[1:])
 
for i in range(1 << n):
    l = [0]*m
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            tmp += price[j]
            for x in range(m):
                l[x] += a[j][x]
    if all(x >= X for x in l):
        ans = min(ans, tmp)
 
print(-1 if ans == 10**9 else 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):
n, m, x = map(int,input().split())
li = [[] for i in range(n)]
minm = 10000000
argl = [0] * m
for i in range(n):
    li[i] = list(map(int,input().split()))

def a(item, money, arg):
    if item == n:
        return 10000000

    nobuy = a(item + 1, money, arg)
    
    newarg = arg.copy()
    for i in range(m):
        newarg[i] += li[item][i + 1]
    
    flg = True
    for i in range(m):
        if newarg[i] < x:
            flg = False
    if flg:
        buy = money + li[item][0]
    else:
        buy = a(item + 1, money + li[item][0], newarg)
    
    return min(buy, nobuy)

res = a(0, 0, argl)
if res == 10000000:
    print(-1)
else:
    print(res)

Solution (Python):
import sys
import numpy as np

def ls_add(l0,l1):
	return [l0[i] + l1[i] for i in range(len(l0))]

n,m,x = [int(e) for e in input().split(" ")[:3]]

book_ls = []
for i in range(n):
	inp_ls = [int(e) for e in input().split(" ")[:m+1]]
	
	book_ls.append(inp_ls)

book_np_ls = np.array(book_ls)
all_sum = np.sum(book_np_ls, axis = 0)
all_result = np.count_nonzero(all_sum[1:] < x)


if all_result > 0:
	print("-1")
	sys.exit()

sum_dic = {tuple([i]): book_ls[i] for i in range(n)}
for i in range(1,n):
	key_ls = [e for e in list(sum_dic) if len(e) == i]
	for e in key_ls:
		ls0 = sum_dic[e]
		max_e = e[-1]
		for ee in range(max_e+1,n):
			ls1 = sum_dic[tuple([ee])]
			temp_ls = ls_add(ls0, ls1)
			sum_dic[tuple(list(e) + [ee])] = temp_ls

min_val = all_sum[0]
for key in sum_dic:
	temp_ls = sum_dic[key]
	flag_ls = [int(e < x) for e in temp_ls[1:]]
	if sum(flag_ls) != 0: continue
	if temp_ls[0] < min_val: min_val = temp_ls[0]

print(min_val)

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

b = [i for i in range(N)]
n = len(b)

b_pairs = []
for i in range(1, n+1):
    b_pairs += list(itertools.combinations(b, i))

cnt = 0
A = [0] * M
B = []
C = []
for i in range(2 ** N - 1):
  w = len(b_pairs[i])
  for j in range(M):
    for k in range(w):
      A[j] += l[b_pairs[i][k]][j + 1]
  B.append(A)
  A = [0] * M
  
for i in range(2 ** N - 1):
  w = len(b_pairs[i])
  for k in range(w):
    cnt += l[b_pairs[i][k]][0]
  C.append(cnt)
  cnt = 0

for i in range(len(B)):
  for j in range(M):
    if B[i][j] >= X:
      pass
    else:
      B[i] = 0
      break
if B == [0] * len(B):
  print(-1)
  exit()

for i in range(len(B)):
  if B[i] != 0:
    B[i] = C[i]
  else:
    B[i] = 1000000000000

print(min(B))

Solution (Python):

i = list(map(int, input().split()))
numBook  = i[0]
numTopic = i[1]
minKnow = i[2]
i=0
j=0 

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



for i in range(1,numTopic+1)	:
	knowledge = 0
	cost_out = 0
	for j in range(0,numBook)	:
		knowledge += Mat[j][i] 
		cost_out += Mat[j][0]
	if knowledge < minKnow	:
		print("-1")
		exit()	




for i in range(0,2**numBook)  :
	bin_str = format(i, '012b')

	
	for i in range(1,numTopic+1)	:
		knowledge = 0
		cost = 0
		for j in range(0,numBook)	:
			knowledge += Mat[j][i] *int(bin_str[11-j])
			cost += Mat[j][0] * int(bin_str[11-j])

		if knowledge < minKnow	:

			break
	
	if cost != 0 	:
		if j == numBook-1 :
			if knowledge >= minKnow	:
				if cost < cost_out:
					cost_out = cost
					
print(cost_out)

Solution (Python):
from itertools import combinations
from sys import maxsize

def check(ls, x):
    for i in ls:
        if i < x:
            return False
    return True


n, m, x = map(int, input().split())
ls = []
a = [i for i in range(n)]
for i in range(n):
    ls.append(list(map(int, input().split())))
total_cost = maxsize
for i in range(1, n + 1):
    comb = list(combinations(a, i))
    for j in comb:
        mo = [0 for p in range(m)]
        cost = 0
        for k in j:
            cost += ls[k][0]
            for h in range(m):
                mo[h] += ls[k][h + 1]
        if check(mo, x):
            total_cost = min(total_cost, cost)

if total_cost ==maxsize:
    print(-1)
else:
    print(total_cost)

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

z = [i for i in range(1, N+1)]
m = [1000000000000000000]

for i in range(N):
    x = list(itertools.combinations(z,i+1))

    for s in x:

        for k in range(1,M+1):
            C = sum(A[j-1][k] for j in s)
            if C < X:
                break
        else:
            m.append(sum(A[o-1][0] for o in s))

print(min(m) if min(m)!=1000000000000000000 else -1)

Solution (Python):
import itertools
import numpy as np
N,M,X=map(int,input().split())
lista=[]
for i in range(N):
    lista.append(list(map(int,input().split())))
lista=np.array(lista)
cost=1000000000000000
judge=[X]*M
data=[k for k in range(1,N+1)]
for i in range(1,N+1):
    a=list(itertools.combinations(data,i))
    for j in a:
        clist=np.array([0]*(M+1))
        for k in j:
            clist=clist+lista[k-1]
        if all(clist[1:]>=judge):
            if clist[0]<cost:
                cost=clist[0]
                m=j
c=0
try:
    for i in m:
        c+=lista[i-1][0]

    print(c)
except:
    print(-1)

Solution (Python):
n, m, x = map(int, input().split())
c = list()
a = list()
for i in range(n):
  row_input = list(map(int, input().split()))
  c.append(row_input[0])
  a.append(row_input[1:])
inf_value = 2*sum(c)
def choose_next_row(partial_choice):
  if len(partial_choice) == n:
    if all(sum(partial_choice[i]*a[i][j] for i in range(n))>=x for j in range(m)):
      return sum(include*cost for include, cost in zip(partial_choice, c))
    else:
      return inf_value
  return min(choose_next_row(partial_choice+[0]), choose_next_row(partial_choice+[1]))
ans = choose_next_row([])
if ans == inf_value:
  print(-1)
else:
  print(ans)

Solution (Python):
import numpy as np

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

a = np.zeros((N,M+1))

for i in range(N):
    
    a[i] = [int(x) for x in input().split()]

b = np.zeros(N)
c = np.zeros(M+1)
min_cost = 9999999999999999

for i in range(2**N):
    ii = i
    for j in range(N):
        b[j] = ii % 2
        ii = ii // 2
    c = np.zeros(M+1)
    flg = "ok"
    for k in range(M+1):
        for j in range(N):
            c[k] += a[j,k] * b[j]
        if k > 0 and c[k] < X:
            flg = "ng"
            continue
    if flg == "ok":
        min_cost = min(min_cost,c[0])

if min_cost == 9999999999999999:
    print(-1)
else:
    print(int(min_cost))

Solution (Python):
import itertools
n,m,x=map(int,input().split())
c=[]
a=[]
ans=float("inf")

for i in range(n):
    tmp=list(map(int,input().split()))
    c.append(tmp[0])
    a.append(tmp[1:])
for i in itertools.product([0,1],repeat=n):
    understand=[0]*m
    tmp=0
    for t,j in enumerate(i):
        if j==1:
            for u,k in enumerate(a[t]):
                understand[u]+=k
            tmp+=c[t]
    if ans>tmp and min(understand)>=x:
        ans=tmp
print(ans) if ans != float("inf") else print(-1)

Solution (Python):
import itertools
import sys

n, m, x = map(int, input().split())
num = list(list(map(int, input().split())) for i in range(n))

s = [i for i in range(n)]
t = []
list_num = []

for i in range(n):
  t.append(list(map(list, itertools.combinations(s, i + 1))))


for i in t:
  for j in i:
    k = [0] * (m + 1)
    for z in j:
      k = tuple(x + y for (x,y) in zip(k, num[z]))
    list_num.append(k)


list_num = list(sorted(list_num, key =lambda w : w[0]))
q = []

flag2 = 0

for i in list_num:
  flag = 1
  for j in range(1, m + 1):
    if(i[j] < x):
      flag = 0
  if(flag == 1):
    q.append(i[0])
    flag2 = 1

if(flag2 == 1):
  print(min(q))
else: 
  print(-1)

Solution (Python):


import itertools

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


min_a = 10000000000000

for i in range(1, N+1):
    for team in itertools.combinations(Cs, i):
        money = [0] * (M+1)
        for t in team:
            money = [i+j for i,j in zip(money,t)]
        flag = 1
        for m in money[1:]:
            if m < X:
                flag = 0
        if flag == 1 and min_a > money[0]:
            min_a = money[0]
if min_a == 10000000000000:
    print(-1)
else:
    print(min_a)

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

for i in range(2 ** n):
    tmp_price = 0
    lst = [0] * (m + 1)
    for j in range(n):
        if((i >> j) & 1):
            lst = [z + y for (z, y) in zip(lst, ca[j])]
    a = lst[1:]

    if all(t >= x for t in a):
        tmp_price = lst[0]
        price = min(tmp_price, price)

if price != 10**10:
    print(price)
else:
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

n, m, x = list(map(int, input().split()))
lis = [list(map(int, input().split())) for i in range(n)]
ans = float('inf')
ima = [0]*m
def solve(i,ima,sum):
  newima=[0]*m
  
  
  
  
  global ans
  mini = float('inf')
  for j in range(m):
    if ima[j] <= mini:
      mini = ima[j]
  
  if mini >= x:
    if sum <= ans:
      ans = sum
      return
 
  if i == n:
    return
  for j in range(m):
    newima[j]=ima[j]+lis[i][j+1]
  solve(i+1, newima, sum+lis[i][0])
  solve(i+1, ima, sum)
  
solve(0, ima, 0)
if ans == float('inf'):
  ans = -1
print(ans)

Solution (Python):

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

A = [0]*M
for ca in CA:
    for i in range(1,M+1):
        a = ca[i]
        A[i-1]+=a
        
if min(A) < X:
    print(-1)
else:
    K = 2**N
    ans = inf
    for i in range(K):
        b = bin(i)
        b = b.lstrip("0b")
        while (len(b)) < N:
            b = "0"+b
            
        A = [0]*M
        cost = 0
        for j in range(N):
            if b[j] == "1":
                ca = CA[j]
                for k in range(M+1):
                    if k == 0:
                        cost+=ca[k]
                    else:
                        A[k-1] += ca[k]
                        
        if min(A) >= X:
            ans = min(ans,cost)
            
    print(ans)

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

li = []
ans = 10**10

def make_list():
    global li
    if len(li) == n:
        hantei()
    else:
        li.append(0)
        make_list()
        li.pop(-1)
        li.append(1)
        make_list()
        li.pop(-1)

def hantei():
    global li, ans
    money = 0
    rikai = [0]*m
    for i,e in enumerate(li):
        if e:
            money += c[i]
            for j in range(m):
                rikai[j] += a[i][j]
    if all((rikai[i] >= x for i in range(m))):
        ans = min(ans, money)

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

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

ans = 1234567890123

for bit in range(1<<n):
    syu = [0]*m
    cost = 0
    for i in range(n):
        if (bit>>i)&1:
            cost += ca[i][0]
            for j in range(1,m+1):
                syu[j-1] += ca[i][j]
    ok = True
    if all(a >= x for a in syu):
        ans = min(ans,cost)
print(ans if ans != 1234567890123 else -1)

Solution (Python):
import itertools

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

ans = []
cost = []
for i in range(1, N+1):
    comb_list = itertools.combinations(C, i)
    for comb in comb_list:
        cost_tmp = 0
        ans_tmp = [0] * M
        for c in comb:
            cost_tmp += c[0]
            ans_tmp = [t+c for t, c in zip(ans_tmp, c[1:])]
        cost.append(cost_tmp)
        ans.append(ans_tmp)

ans_result = [all([aa >= X for aa in a]) for a in ans]
try:
    res = min([c for a, c in zip(ans_result, cost) if a])
except:
    print(-1)
    exit()

print(res)

Solution (Python):
n, m, x = list(map(int, input().split()))
books = []
dp = [[0]*(m+1) for i in range(2**(n))]
for i in range(n):
    book = list(map(int, input().split()))
    books.append(book)

    
min_cost = -1


for i in range(2**(n)):
    if i == 0:
        continue
    refbook = 0
    keta = 0
    for j in range(13):
        if (i >> j) % 2 == 1:
            refbook += 2**j
            keta = j
        elif i >> j == 0:
            refbook -= 2**(keta)
            break
    refbook = max(0, refbook)   
    checker = True
    for k in range(m+1):
        dp[i][k] = dp[int(refbook)][k] + books[keta][k]
        if k != 0 and dp[i][k]<x:
            checker = False
            
    if checker:
        if min_cost == -1:
            min_cost = dp[i][0]
        else:
            min_cost = min(min_cost, dp[i][0])
          
print(min_cost)

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):
from collections import defaultdict

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

ans_min = -1
for i in range(2**N):
    ans = 0
    m = defaultdict(int)
    for j in range(N):
        if (i >> j) & 1:
            ans += C[j]
            for index, k in enumerate(A[j]):
                m[index] += k

    if len(m.values()) != 0 and all(v >= X for v in m.values()):
        if ans_min == -1:
            ans_min = ans
        else:
            ans_min = min(ans, ans_min)
print(ans_min)

Solution (Python):
import numpy as np
import itertools

N, M, X = map(int, input().split())
CA = np.zeros((N, M + 1))

for i in range(N):
    CA[i, :] = [int(x) for x in input().split()]

min_price = float('inf')
All = [i for i in range(N)]

for x in range(1, N + 1):
    for comb in list(itertools.combinations(All, x)):
        if min(CA[comb, 1:].sum(axis=0)) >= X and CA[comb, 0].sum() < min_price:
            min_price = CA[comb, 0].sum()
        else:
            pass

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

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

ans = 1234567890123

for bit in range(1<<n):
    syu = [0]*m
    cost = 0
    for i in range(n):
        if (bit>>i)&1:
            cost += ca[i][0]
            for j in range(1,m+1):
                syu[j-1] += ca[i][j]
    ok = True
    if not False in list(map(lambda a: a >= x,syu)):
        ans = min(ans,cost)
print(ans if ans != 1234567890123 else -1)

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):
import numpy as np
import itertools


def main():
    N, M, X = (int(x) for x in input().split())
    A = [[int(x) for x in input().split()] for i in range(N)]
    A.sort()
    a = np.array(A)
    t = []
    ans = []
    for i in range(1, N + 1):
        C = list(itertools.combinations(A, i))
        for c in C:
            k = np.array(c)
            k = k.sum(axis=0)
            ans.append(is_ok(X, k))
    for i in ans:
        if i != -1:
            t.append(i)
    
    if t:
        print(min(t))
    else:
        print(-1)


def is_ok(X, k):
    M = len(k)
    f = list(map(lambda x: x >= X, k[1:M]))
    if False not in f:
        return k[0]
    else:
        return -1


if __name__ == "__main__":
    main()

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

books = []
books.append(list(map(int, input().split())))
for i in range(n-1):
    item = list(map(int, input().split()))
    books.append(item)

und = [0] * m

for b in books:
    for i in range(m):
        und[i] += b[i+1]

flag = True
for i in range(m):
    if und[i] < x:
        flag = False
        break

if flag == False:
    print(-1)
else:
    b = 0
    ans = float('inf')
    for i in range(2**n-1):
        b +=1
        und = [0] * m
        tmp = format(b,'b').zfill(n)
        tmp_ans = 0
        for j in range(n):
            tmp_ans += books[j][0]*int(tmp[j])
            for k in range(m):
                und[k] += books[j][k+1]*int(tmp[j])

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

        if flag and tmp_ans < ans:
            ans = tmp_ans

    print(ans)

Solution (Python):
import itertools
import numpy as np

mNMX = map(int, input().split())
lNMX = list(mNMX)

mBook = [map(int, input().split()) for i in range(lNMX[0])]
lBook = [list(mBook[i]) for i in range(lNMX[0])]
nBook = np.array(lBook)
mPrice = 10 ** 8

for i in range(0, lNMX[0]):
    combi = itertools.combinations(range(0, lNMX[0]), i + 1)
    for c in combi:
        cBook = nBook[c, :]
        sBook = np.sum(cBook, axis = 0)
        comp = [0 if i >= lNMX[2] else -1 for i in sBook[1:]]
        if(sum(comp) == 0):
            mPrice = sBook[0] if sBook[0] < mPrice else mPrice
    
print(mPrice if mPrice <= 12 * 10 ** 5 else -1)

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

A = [0]*M
for i in range(N):
    for k in range(M):
        A[k] += CA[i][k+1]
for i in range(M):
    if A[i] < X:
        print('-1')
        exit() 

price = 0
ans = 10**10
A = [0]*M
for i in range(2**N):
    list = [1]*N
    for j in range(len(list)):
        if (i>>j) & 1:
            list[j] = 0
        price = 0
        A = [0]*M
        for k in range(N):
            if list[k] == 1:
                for s in range(M):
                    A[s] += CA[k][s+1]
                price += CA[k][0]
    if all(A[m] >= X for m in range(M)):
        ans = min(ans,price)
print(ans)

Solution (Python):
import itertools 
def solve():
    n, m, x = map(int, input().split())
    c = []
    a = []
    for _ in range(n):
        C, *A = map(int, input().split())
        c.append(C)
        a.append(A)

    ans = n*1e8
    for i in range(n):
        for j in itertools.combinations(range(n), i+1):
            cnt = [0]*m
            for k in j:
                for l in range(m):
                    cnt[l] += a[k][l]
            for s in range(m):
                if cnt[s] < x:
                    break
                if s == m-1:
                    num = 0
                    for q in j:
                        num += c[q]
                    ans = min(ans, num)
    if ans == n*1e8:
        ans = -1
            
    return ans
    

print(solve())

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

mincost = 0
for i in range(n):
    mincost += l[i][0]

s = []
for i in range(m+1):
    s.append(0)

flag = 0

for i in range(2 ** n):
    cost = 0
    for j in range(n):
        if ((i >> j) & 1):
            cost += l[j][0]
            for k in range(1, m+1):
                s[k] += l[j][k]
    b = 1
    for k in range(1, m+1):
        if s[k] < x:
            b = 0 
    if b == 1:
        flag = 1
        mincost = min(cost, mincost)
    for i in range(m+1):
        s[i] = 0

if flag == 1:
    print(mincost)
else:
    print(-1)