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())
C = []
A = []
for i in range(N):
    line = list(map(int, input().split()))
    C.append(line[0])
    A.append(line[1:])

limit = 2 ** N
ans = (10 ** 5) * 13
for p in range(limit):
    t = 1
    U = [0] * M
    cost = 0
    for i in range(N):
        if p & t > 0:
            cost += C[i]
            for j in range(M):
                U[j] += A[i][j]
        t <<= 1
    if all([su >= X for su in U]):
        ans = min(cost, ans)

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

Solution (Python):


def list_sum(a, b):
    n = len(a)
    c = [0] * n
    for i in range(n):
        c[i] = a[i] + b[i]
    return c

def skilled(ca_sum, x):
    m = len(ca_sum) - 1
    ret = True
    for i in range(1, m+1):
        ret = ret and ca_sum[i] >= x
    return ret

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

    for i in range(2 ** n):
        ca_sum = [0] * (m+1)
        for j in range(n):
            if (i >> j) & 1:
                ca_sum = list_sum(ca_sum, ca[j])
        if skilled(ca_sum, x):
            c_list.append(ca_sum[0])

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

if __name__ == '__main__':
    main()

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')

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


res = INF
for i in range(2 ** N):
    books = []
    for j in range(N):
        if i & (1 << j):
            books.append(C[j])
    total = 0
    level = [0] * M
    for book in books:
        total += book[0]
        for idx, l in enumerate(book[1:]):
            level[idx] += l
    flag = True
    for lev in level:
        if lev < X:
            flag = False
    if flag:
        res = min(res, total)

if res == INF:
    print('-1')
else:
    print(res)

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

flg = False
ans = 10**12
for i in range(2**N):
    A = []
    for j in range(N):
        if ((i>>j) & 1):
            A.append(P[j])

    value = 0
    algo = [0]*M
    for a in A:
        value += a[0]
        for i in range(1, M+1):
            algo[i-1] += a[i]

    cnt=0
    for al in algo:
        if al>=X:
            cnt+=1
    if cnt==M:

        flg=True
        ans = min(ans, value)
if flg:
    print(ans)
else:
    print(-1)

Solution (Python):
N, M, X = map(int, input().split())
CA = []
for i in range(N):
  karilist = list(map(int, input().split()))
  CA.append(karilist)
ans = 0
for i in range(M):
  rikai = 0
  for j in range(N):
    rikai += CA[j][i+1]
  if rikai < X:
    ans = -1
    break

if ans == 0:
  ans = N*(10**5)
  for j in range(2**N):
    dame = 0
    rikaiM = [0 for i in range(M)]
    cost = 0
    for k in range(N):
      if (j >> k) & 1 == 1:
        cost += CA[k][0]
        for h in range(M):
          rikaiM[h] += CA[k][h+1]
    
    for h in rikaiM:
      if h < X:
        dame = 1
        break
    if dame == 0:
      ans = min(ans, cost)
print(ans)

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

A = [[0] * m for _ in range(n)]
C = [0] * n

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



from itertools import product
bit = [0, 1]
lst = product(bit, repeat=n)


INF = 1 << 40
m_min = INF
for v in lst:
	res = [0] * m
	money = 0
	for i in range(n):
		if v[i] == 1: 
			for x in range(m):
				res[x] += A[i][x]
			money += C[i]
	if all([e >= X for e in res]):
		m_min = min(m_min, money)

print(m_min) if m_min != INF else print(-1)

Solution (Python):
import itertools

N, M, X = map(int, input().split())
ca = []
for _ in range(N):
  ca.append(list(map(int, input().split())))
  
ns = [i for i in range(N)]
price = 1000000000000
for r in range(1,N+1):
  for v in itertools.combinations(ns, r):
    flag = True
    for j in range(M):
      s = sum([ca[i][j+1] for i in v])
      if s < X:
        flag = False
        continue
    if flag:
      p = sum([ca[i][0] for i in v])
      price = min(price, p)
      
if price == 1000000000000:
  print(-1)
else:
  print(price)

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

i=0
while i<N:
    C[i]=list(map(int,input().split()))
    i+=1

ans=10**9
for i in range(2 ** N):
    bag = [0]*M
    total=0
    for j in range(N):  
        if ((i >> j) & 1):  
            a=0    
            for k in C[j][1:]:
                bag[a]+=k
                a+=1
            total+=C[j][0]  
    if all(b>=X for b in bag):
        ans=min(ans,total)
    
if ans==10**9:
    print(-1)
else:
    print(ans)

Solution (Python):

import itertools
N, M, X = map(int, input().split())
C_list = []
A_list_list = []
for i in range(N):
    A_list = list(map(int, input().split()))
    C_list.append(A_list[0])
    A_list_list.append(A_list[1:])

N_list = [i for i in range(N)]
ans = 10 ** 10
for i in range(1, N + 1):
    for comb in itertools.combinations(N_list, i):
        temp_ans = 0
        for j in comb:
            temp_ans += C_list[j]
        if temp_ans >= ans:
            continue
        
        X_list = [0 for _ in range(M)]
        for j in comb:
            temp_A_list = A_list_list[j]
            for k in range(M):
                X_list[k] += temp_A_list[k]
        if len([X_list[i] for i in range(len(X_list)) if X_list[i] < X]) == 0:
            ans = min(ans, temp_ans)

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

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

purchase_l = [0]*n
cost = float('inf')
flag = True

while flag:
    skill = [0]*m
    cost_tmp = 0
    for i in range(n):
        for j in range(m):
            skill[j] += purchase_l[i]*ca[i][j+1]
    for s in skill:
        if s < x:
            break
    else:
        for i in range(n):
            cost_tmp += purchase_l[i]*ca[i][0]
        cost = min(cost, cost_tmp)
    for k in range(1,n+1):
        purchase_l[-k] += 1
        if purchase_l[-k] == 2:
            purchase_l[-k] = 0
        else:
            break
    else:
        flag = False

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

Solution (Python):
import itertools

n,m,x=map(int,input().split())
kin=[]
rika=[]
ans=10000000
for i in range(n):
    tmp=list(map(int,input().split()))
    kin.append(tmp[0])
    rika.append(tmp[1:])

tmpp=[0]*m
for i in range(1,n+1):
    for j in itertools.combinations(range(1,n+1), i):
        tmpp = [0] * m
        
        for k in j:
            for l in range(m):
                tmpp[l]+=rika[k-1][l]
        
        if min(tmpp)>=x:
            kincou=0
            for k in j:
                kincou+=kin[k-1]
            ans=min(ans,kincou)
if ans==10000000:
    print(-1)
else:
    print(ans)

Solution (Python):
n, m, x = [int(i) for i in input().split()]
arr = []

for _ in range(n):
    arr.append([int(i) for i in input().split()])

min_amount = float('+inf')
has_sol = False

def dfs(idx, amt, skills):
    global arr
    global min_amount
    global x
    global has_sol

    if idx == len(arr):
        ok = all(j >= x for j in skills)

        if ok:
            has_sol = True
            min_amount = min(min_amount, amt)
        return

    dfs(idx+1, amt, skills)
    dfs(idx+1, amt+arr[idx][0], [j+arr[idx][i+1] for i, j in enumerate(skills)])

dfs(0, 0, [0]*m)

if not has_sol:
    print('-1')
else:
    print(min_amount)

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

sum=[0]*(m+1)
minval=1200001
for i in range(0,2**n):
    sum=[0]*(m+1)
    for j in range(n-1,-1,-1):
        if i//(2**j)==1:
            for k in range(0,m+1):
                sum[k]+=a[j][k]
        i = i % (2**j)
    flag=0
    for l in range(1,m+1):
        if sum[l] < x:
            flag=1
            break;
    if flag==0:
        minval= min(minval,sum[0])

if minval==1200001:
    print("-1")
else:
    print(minval)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


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

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  

N, M, X = read_ints()
C, *A = read_col(N)


def ret_each_exp(p):
    exps = [0] * M
    money = 0
    
    for i, pp in enu(p):
        if pp == 0:
            continue
        for m in range(M):
            exps[m] += A[m][i]
        money += C[i]
    return exps, money


def is_valid(exps):
    for e in exps:
        if e < X:
            return False
    return True


ans = INF
for p in product(range(2), repeat=N):
    exps, money = ret_each_exp(p)
    if is_valid(exps):
        ans = min(ans, money)
print(ans if ans != INF else -1)

Solution (Python):
n, m, x = map(int, input().split())
sL = [0]*m
bL = []
for i in range(n):
    book = list(map(int, input().split()))
    bL.append(book)


def fullS(currentL, index, allP):
    if index >= len(bL):
        if min(currentL) >= x:
            return allP
        else:
            return -1
    else:
        if min(currentL) >= x:
            return allP
        else:
            op1 = fullS(currentL, index+1, allP)
            newP = 0
            newL = []
            for i in range(len(bL[index])):
                if i == 0:
                    newP = allP+bL[index][i]
                else:
                    newL.append(currentL[i-1]+bL[index][i])
            op2 = fullS(newL, index+1, newP)
            if op1 == -1 and op2 == -1:
                return -1
            elif op1 == -1:
                return op2
            elif op2 == -1:
                return op1
            else:
                return min(op1, op2)
                


print(fullS(sL, 0, 0))

Solution (Python):
N,M,X=map(int,input().split())
dic=[]
ans=10**18
ans_check=[0]*M
ans_t=0
for _ in range(N):
    dic.append(list(map(int,input().split())))
for i in range(0,2**N):
    tmp=i
    ans_t=0
    flag=0
    ans_check=[0]*M
    for j in range(N):
        index=tmp%2
        tmp=tmp//2
        if index==1:
            ans_t+=dic[j][0]
            for t in range(1,M+1):
                ans_check[t-1]+=dic[j][t]
    
    for d in ans_check:
        if d>=X:
            flag=1
        else:
            flag=0
            break
    if flag==1:
        ans=min(ans,ans_t)
    
if ans==10**18:
    print(-1)
else:
    print(min(ans,ans_t))

Solution (Python):
import itertools

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

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

C_total_min = -1
for ci in range(1, N+1):  
    for seq in itertools.combinations(range(N), ci): 
        C_total = 0
        A_total = [0] * M
        for ni in seq:
            C_total += C[ni]
            A_total = [A_total[ai] + A[ni][ai] for ai in range(M)]

        
        flag = True
        for ai in range(M):
            if A_total[ai] < X:
                flag = False
        if flag: 
            if C_total_min == -1:
                C_total_min = C_total
            elif C_total_min > C_total:
                C_total_min = C_total
            else:
                pass

print(C_total_min)

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

s = float('inf')

for i in range(2 ** N):
    rikai = [0] * M
    total = 0
    is_rikai = True
    for j in range(N):
        if ((i >> j) & 1):
            total += (ca[j][0])
            for k in range(1, M + 1):
                rikai[k - 1] += ca[j][k]
    for l in rikai:
        if l < X:
            is_rikai = False
    if is_rikai:
        s = min(s, total)

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

Solution (Python):
n, m, x = [int(v) for v in input().split()]

c = [0] * n
a = [[] * m for i in range(n)]
for i in range(n):
    line = [int(v) for v in input().split()]
    c[i] = line[0]
    a[i] = line[1:]

ans = sum(c)
can = False
for i in range(1, 2 ** n):
    sumv = [0] * m
    sumc = 0
    for j in range(n):
        has_bought = i & 1
        if has_bought:
            sumc += c[j]
            for k in range(m):
                sumv[k] += a[j][k]
        i = i >> 1
    can = True
    for k in range(m):
        if sumv[k] < x:
            can = False
            break
    if can:
        ans = min(ans, sumc)

if can:
    print(ans)
else:
    print(-1)

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, X = map(int, readline().split())

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

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

isPossible = True
for col in range(M):
    tmp = 0
    for row in range(N):
        tmp += A[row][col]
    if tmp < X:
        isPossible = False

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

res = sum(C)
for b in range(1 << N):
    isPossible = True
    tmp = 0
    acc = [0 for j in range(M)]
    for i in range(N):
        if b & 1 << i > 0:
            tmp += C[i]
            for j in range(M):
                acc[j] += A[i][j]

    for j in range(M):
        if acc[j] < X:
            isPossible = False
    if isPossible:
        res = min(res, tmp)
print(res)

Solution (Python):


import itertools

def main():

    s = [int(x) for x in input().split(' ')]
    n = s[0]
    m = s[1]
    x = s[2]

    iters = []
    ran = range(n)
    for i in range(n):
        comb = list(itertools.combinations(ran, i+1))
        iters.extend(comb)

    books = []
    for j in range(n):
        l = [int(x) for x in input().split(' ')]
        books.append(l)

    sum_list = []
    for comb in iters:
        flag = False
        budget = []
        score_list = [0 for x in range(m)]
        for index in comb:
            book = books[index]
            budget.append(book[0])
            book_score = book[1:]
            for i, bs in enumerate(book_score):
                score_list[i] += bs
            flags = [True if y >= x else False for y in score_list]
            flag = all(flags)
        if flag:
            sum_list.append(sum(budget))
    if len(sum_list) == 0:
        print(-1)
    else:
        print(min(sum_list))

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations

N, M, X = [ int(i) for i in input().strip().split(' ') ]

C = []
A = []
A_sum = [0] * M
for i in range(N):
    data = [ int(i) for i in input().strip().split(' ') ]
    C.append(data[0])
    A.append(data[1:])
    for j in range(M):
        A_sum[j] += data[j+1]

if min(A_sum) < X:
    print('-1')
else:
    min_C = float('inf')
    for n_select in range(1, N+1):
        for cmb in combinations(range(N), n_select):
            A_sum = [0] * M
            C_sum = 0
            for i in cmb:
                for j in range(M):
                    A_sum[j] += A[i][j]
                C_sum += C[i]
            if (C_sum < min_C) and (min(A_sum) >= X):
                min_C = C_sum
    print(min_C)

Solution (Python):
import itertools

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

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

a = itertools.product(range(2), repeat=n)



cost = 100000000

for pr in list(itertools.product(range(2),repeat=n)):

	skill = [0 for i in range(m+1)]
	tcost = 0
	for i in range(n):
		if(pr[i] == 1):
			tcost+=ca[i][0]
			for j in range(1,m+1):
				skill[j]+=ca[i][j]
	

	
	flag = 1
	for j in range(1,m+1):
		if(skill[j] < x):
			flag=0
	if(flag==1):
		cost=min(cost,tcost)
		
if(cost == 100000000):
	print(-1)
else:
	print(cost)

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

num = [0,1]
p = itertools.product(num,repeat = n)

for i in p:
    tmp = [0 for i in range(m)]
    tmpans = 0
    for j in range(len(i)):
        if i[j] == 1:
            tmpans += c[j]
            for k in range(m):
                tmp[k] += a[j][k]
    if min(tmp) >= x:
        ans.append(tmpans)
if ans:
    print(min(ans))
else:
    print(-1)

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

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

for i in range(1, 2**n):
    money = 0
    skill = [0]*m
    for j in range(n):
        if (i >> j) & 1:
            money += C[j][0]
            for k in range(1, m+1):
                skill[k-1] += C[j][k]
    
    t = 0
    for sk in skill:
        if sk < x:
            t += 1
    if t == 0:
        ans = min(ans, money)
    

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

Solution (Python):
from operator import add
N, M, X = map(int, input().split())

price = []
effect = []
for _ in range(N):
    C, *A = map(int, input().split())
    price.append(C)
    effect.append(A)

ans = 10**10
flg = False
for bit in range(2**N):
    tmp_price = 0
    tmp = [0 for _ in range(M)]
    for i in range(N):
        if (1 << i) & bit:
            tmp = map(add, tmp, effect[i]) 
            tmp_price += price[i]

    if min(tmp) >= X:
        flg = True
        ans = min(ans, tmp_price)

if flg:
    print(ans)
else:
    print(-1)

Solution (Python):
import numpy as np
N, M, X = map(int, input().split())

CA = [list(map(int, input().split())) for _ in range(N)]
CA = np.array(CA)
C = [CA[i][0] for i in range(N)]

ans = sum(C)

Flag = False

for i in range(2 ** N):
    A_count = np.zeros(M)
    C_count = 0
    bin_str = format(i, 'b')
    if len(bin_str) < N:
        bin_str = '0' * (N - len(bin_str)) + bin_str
    for j, s in enumerate(bin_str):
        if s == '1':
            A_count = A_count + CA[j][1:]
            C_count += CA[j][0]
    flag = True
    for k in range(M):
        if A_count[k] < X:
            flag = False
            break
    if flag and C_count <= ans:
        ans = C_count
        Flag = True

if Flag == False:
    print(-1)
else:
    print(ans)

Solution (Python):

import numpy as np

def solve(N, M, X, C, A):
    A = np.array(A)

    max_iq_list = sum(A)
    if min(max_iq_list) < X:
        print(-1)
        return

    cost_list = []
    for i in range(1, 2**N):
        book = []
        cost = 0
        for j in range(N):
            if ((i >> j) & 1):
                book.append(A[j])
                cost += C[j]
        if min(sum(np.array(book))) < X:
            pass
        else:
            cost_list.append(cost)

    print(min(cost_list))

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

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    x = [int(i) for i in input().split()]
    c, a = x[0], x[1:]
    C.append(c)
    A.append(a)
over = 1000000000
ans = over
for Z in itertools.product(range(0, 2), repeat=N):
    ctotal = 0
    atotal = [0] * M
    for i in range(N):
        if Z[i] == 1:
            ctotal += C[i]
            for j in range(A[i].__len__()):
                atotal[j] += A[i][j]
    ok = True
    for a in atotal:
        if a < X:
            ok = False
    if ok:
        ans = min(ans, ctotal)

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

Solution (Python):
def sumList(index,array):
    if index ==n:
        sumArray.append(array)
    else:
        sumList(index+1,array)
        nextArray =[0]*(m+1)
        for i in range(m+1):
            nextArray[i] +=array[i]+ list[index][i]
        sumList(index+1,nextArray)



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

    list = []
    for i in range(n):
        a = [int(i) for i in input().split()]
        list.append(a)
    firstArray = [0] * (m + 1)
    sumArray = []
    sumList(0,firstArray)

    min = 100000000
    for i in sumArray:
        amount =0
        count =0
        for j in range(len(i)):
            if j == 0:
                amount =i[j]
            else:
                if i[j] >=x:
                    count+=1
        if count == m and min >= amount:
            min = amount

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

Solution (Python):
def main():
    from builtins import int, map, list, float, print, len, min
    from itertools import combinations
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N, M, X = input_number_list()
    C = []
    A = []
    for i in range(N):
        sc = input_number_list()
        C.append(sc[0])
        A.append(sc[1:])
    ls = []
    idxs = [i for i in range(N)]
    for i in range(0, N):
        for combi in combinations(idxs, i + 1):
            ls.append(combi)
    ans = float('inf')
    for i in range(len(ls)):
        money = 0
        xs = [0] * M
        is_ng = False
        for j in range(len(ls[i])):
            money += C[ls[i][j]]
            for k in range(len(A[ls[i][j]])):
                xs[k] += A[ls[i][j]][k]
        for n in range(len(xs)):
            if xs[n] < X:
                is_ng = True
                break
        if is_ng == False:
            ans = min(ans, money)
    if ans == float('inf'):
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for i in range(n)]
min_ = float('inf')


for bit in range(1 << n):

    cost = 0
    alg = [0]*m
    ok = [0]*m
    flag = 0
    for i in range(n):

        if bool(bit & 1<<i) == 1:
            cost += ca[i][0]

            for j in range(1,m+1):
                alg[j - 1] += ca[i][j]
                if alg[j - 1] >= x:
                    ok[j - 1] = 1
        if ok.count(1) >= m:
            flag = 1
            break

    if flag == 1:
        min_ = min(min_,cost)
if min_ == float('inf'):
    print(-1)
else:
    print(min_)

Solution (Python):
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N, M, X = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in [0] * N]

    ans = float('inf')
    for mask in range(1, 1 << N):
        book = []
        for i in range(N):
            if mask & 1 << i:
                book.append(A[i])
        yen = 0
        m = [0] * M
        for a in book:
            yen += a[0]
            for i, v in enumerate(a[1:]):
                m[i] += v
        for i in m:
            if i < X:
                break
        else:
            ans = min(ans, yen)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)


main()

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

n,m,x = MI()
c = [LI() for _ in range(n)]
ans = []

for i in range(2**n):
    c_sum = 0
    a = [0]*m
    for j in range(n):
        c_sum += int(format(i, '0'+ str(n) +'b')[j])*c[j][0]
        for k in range(m):
            a[k] += int(format(i, '0'+ str(n) +'b')[j])*c[j][k+1]
    if min(a) >= x:
        ans.append(c_sum)
if ans == []:
    print(-1)
else:
    print(min(ans))

Solution (Python):
import itertools

N, M, X = list(map(int, input().split()))
c_list = []
a_table = []
for _ in range(N):
    a_list = list(map(int, input().split()))
    a_table.append(a_list[1:])
    c_list.append(a_list[0])

p_list = list(itertools.product([True, False], repeat=N))
min_cost = float("inf")
for pattern in p_list:  
    cost = 0
    rikai_list = [0] * M
    for n, is_buy in enumerate(pattern):  
        
        if not is_buy:
            continue
        cost += c_list[n]
        for m, a in enumerate(a_table[n]):  
            
            rikai_list[m] += a
    not_understand = [r for r in rikai_list if r < X]  
    if not not_understand:
        min_cost = min(min_cost, cost)

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

Solution (Python):
import numpy as np

N, M, X = map(int, input().split())
C = np.zeros(N, dtype=np.int)
A = np.zeros((N, M), dtype=np.int)

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


least_cost = np.inf


for pattern in range(2 ** N):
	knowledge = np.zeros(M, dtype=np.int)
	cost = 0
	
	for i in range(N):
		if (pattern >> i) & 1:
			cost += C[i]
			for j in range(M):
				knowledge[j] += A[i, j]
	
	if np.all(knowledge >= X) and cost < least_cost:
		least_cost = cost


if np.isinf(least_cost):
	print(-1)
else:
	print(least_cost)

Solution (Python):
import sys
import numpy

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, M, X = map(int, readline().split())
    cost = []; A = []
    for _ in range(N):
        c, *Atmp = map(int, readline().split())
        cost.append(c); A.append(Atmp)
    cost = numpy.array(cost)
    A = numpy.array(A)

    pay = []
    for i in range(2**N):
        jtmp = []
        costtmp = 0
        for j in range(N):
            if (i>>j)&1:
                jtmp.append(j)
        costtmp = cost[jtmp].sum()
        brain = A[jtmp,:].sum(axis=0)
        if all(brain >= X):
            pay.append(costtmp)

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


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

c = []
score = []
for _ in range(n):
    inp = list(map(int, input().split()))
    c.append(inp[0])
    score.append(inp[1:])
c = np.array(c)
score = np.array(score)

ans = float('inf')
for i in range(2 ** n):
    scores = np.array([0] * m)
    cost = 0
    for j in range(n):
        if (i >> j) & 1:
            scores += score[j]
            cost += c[j]
    if all(scores >= x):
        ans = min(ans, cost)

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

Solution (Python):
import  itertools
import numpy as np

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


l = [1, 0]
ll = list(itertools.product(l, repeat=N))

ans = float("inf")
for i in ll:
    jdg = np.array([0] * (M+1))
    for k in range(N):
        if i[k] == 1:
             jdg = jdg + A[k]
    
    if min(jdg[1:]) >= X:
        ans = min(ans,jdg[0])
    
if ans != float("inf"):
    print(ans)
else:
    print(-1)

Solution (Python):
import numpy as np
N,M,X= map(int,input().split())
C = [0 for i in range(N)]
A = [[0 for i in range(M+1)] for j in range(N)]
skill = [0 for i in range (M)]
ans = float('inf')
ans_check = 0
for i in range(N):
  A[i] = list(map(int,input().split()))
  C[i] = A[i][0]
A = np.array(A)
for i in range(2 ** N):
 
  skill = np.array([0 for i in range (M)])
  money = 0
  check = 0
  for j in range(N):  
    if ((i >> j) & 1):  
      for l in range(M):
        skill[l] += A[j][l+1]
      money += C[j]
  for k in range(M):
    if skill[k]<X:
      check = 1
      
  if check == 0:
    if money <= ans:
      ans = money
      ans_check = 1
  
if ans_check == 0:
  print(-1)
else:
  print(ans)

Solution (Python):
import math

N, M, X = map(int, input().split())
costs = []
values = []
values_per_algs = [[] for _ in range(M)]
for _ in range(N):
  book = list(map(int, input().split()))
  costs.append(book[0])
  values.append(book[1:])
  for i in range(1, M+1):
    values_per_algs[i-1].append(book[i])

def rec(i, cost, val_per_algs):
  if i==N:
    if sum([1 if vals < X else 0 for vals in val_per_algs]) > 0:
      return math.inf
    else:
      return cost
  tmp_val_per_algs = val_per_algs.copy()
  for j in range(M):
    tmp_val_per_algs[j] += values[i][j]
  return min(rec(i+1, cost+costs[i], tmp_val_per_algs), rec(i+1, cost, val_per_algs.copy()))
  

def main():
  if sum([1 if sum(vals) < X else 0 for vals in values_per_algs]) > 0:
    print(-1)
    return
  print(rec(0, 0, [0 for i in range(M)]))
main()

Solution (Python):
n,m,x=map(int,input().split())
l=[]
for i in range(n):
  s=list(map(int,input().split()))
  l.append(s)
ans=12*(10**5)

import itertools
now=0
oko=0
com=[i for i in range(n)]
while now<=n:
  now+=1
  level=[0 for j in range(0,m+1)]
  for i in itertools.combinations(com, now):
    level=[0 for j in range(m+1)]
    money=0
    
    for h in i:
      
      money+=l[h][0]
      for k in range(1,m+1):
        level[k]+=l[h][k]
    jud=0
    for ii in level:
      if ii>=x:
        jud+=1
    if jud==m:
      oko+=1
      
      ans=min(ans,money)
if oko==0:
  print("-1")
else:
  print(ans)