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

"""AtCoder Beginner Contest 167: C - Skill Up
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""

N, M, X = 0, 0, 0
BOOKS = []


def calc_price(book_combinations):
    price = 0
    understandings = [0] * M
    for i in range(len(book_combinations)):
        if book_combinations[i]:
            price += BOOKS[i][0]
            for j in range(len(BOOKS[i][1:])):
                understandings[j] += BOOKS[i][j + 1]
    for u in understandings:
        if u < X:  
            return -1
    return price


def main():
    global N, M, X, BOOKS
    N, M, X = list(map(int, input().split()))
    BOOKS = [list(map(int, input().split())) for i in range(N)]

    ans = float('inf')
    for i in range(1, 2 ** N):  
        price = calc_price([(i >> j) & 1 for j in range(N)])
        if 0 < price and price < ans:
            ans = price
    if ans == float('inf'):
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  L=list(map(int,input().split()))
  C.append(L[0])
  A.append(L[1:])
ans=-1
for i in range(1<<N):
  cost=0
  tmp=[0]*M  
  for j in range(N):
    if (i>>j)&1==0:
      continue
    cost+=C[j]
    l=0
    for k in A[j]:
      tmp[l]+=k
      l+=1
    if min(tmp)>=X:
      if ans==-1:
        ans=cost
      else:
        ans=min(ans,cost)
print(ans)

Solution (Python):
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  L=list(map(int,input().split()))
  C.append(L[0])
  A.append(L[1:])
ans=-1
for i in range(1<<N):
  cost=0
  tmp=[0]*M
  for j in range(N):
    if (i>>j)&1==0:
      continue
    cost+=C[j]
    for k in range(M):
      tmp[k]+=A[j][k]
    if min(tmp)>=X:
      if ans==-1:
        ans=cost
      else:
        ans=min(ans,cost)
print(ans)

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):
n,m,x = map(int,input().split())
c,a = [],[]
ans = float('inf')
for i in range(n):
    y = list(map(int,input().split()))
    c.append(y.pop(0))
    a.append(y)
for i in range(2**n):
    b = [0]*m
    cost = 0
    for j in range(n):
        if i&(1<<j):
            cost+=c[j]
            for k in range(m):
                b[k]+=a[j][k]
    for j in range(m):
        if b[j]<x:
            break
    else:
        ans = min(ans,cost)
if ans==float('inf'): print("-1")
else: print(ans)

Solution (Python):
import sys
n, m, x = [int(i) for i in sys.stdin.readline().split()]
c_ls = []
a_ls = []
INF = 10**18
for i in range(1,1+n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    c = inp[0]
    a_s = inp[1:]
    c_ls.append(c)
    a_ls.append(a_s)

best = INF
for i in range(1 << n):
    _sum = 0
    scores = [0] * n
    combi = bin(i)[2:].zfill(n)
    for i, c in enumerate(combi):
        if c == "1":
            _sum += c_ls[i]
            scores = [s + a for s, a in zip(scores, a_ls[i])]
    if min(scores) < x:
        continue
    if best > _sum:
        best = _sum
if best == INF:
    print(-1)
else:
    print(best)

Solution (Python):

import sys
import numpy as np
from collections import deque



N,M,X = [int(x) for x in sys.stdin.readline().split()]

g = np.zeros([N,M+1])
for _ in range(N):
    g[_] = [int(x) for x in sys.stdin.readline().split()]

g_split = np.split(g, [1], 1)

money = -1


for i in range(2**N):
    
    money_tmp = 0 
    skill_tmp = np.zeros(M) 
    for j in range(N):
        if(( i >> j ) & 1):
            
            money_tmp = money_tmp + g_split[0][j]
            skill_tmp = skill_tmp + g_split[1][j]
    
    
    if np.all(skill_tmp >= X):
        if money == -1:
            money = int(money_tmp[0])
        elif money > money_tmp:
            money = int(money_tmp[0])

print(money)

Solution (Python):
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  L=list(map(int,input().split()))
  C.append(L[0])
  A.append(L[1:])
res=-1
for i in range(1<<N):
  und=[0]*M
  cost=0
  for j in range(N):
    if (i>>j)&1==0:
      continue
    cost+=C[j]
    for k in range(M):
      und[k]+=A[j][k]
    if min(und)>=X:
      if res==-1:
        res=cost
      else:
        res=min(res,cost)
print(res)

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

A = []
C = []
ans = float("Inf")

for c , *a in book:
    C.append(c)
    A.append(a)

for bit in range(1<<n):
    algo = [0]*m
    cost = 0
    for i in range(n):
        if bit & (1<<i):
            cost += C[i]
            for idx , a in enumerate(A[i]):
                algo[idx] += a
    if all([True if a >= x else False for a in algo]):
        ans = min(ans , cost)

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

Solution (Python):

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

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

result = -1
for i in range(1 << N):
    t = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

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

INF = float('inf')
ans = INF

for i in range(2 ** n):
    bag = []
    score = [0] * m
    flg = True
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(j)

    for j in range(1, m + 1):
        for k in bag:
            inc = a[k][j]
            score[j - 1] += inc

    for k in score:
        if k < x:
            flg = False

    if flg:
        pri = 0
        for j in bag:
            pri += a[j][0]
        if pri < ans:
            ans = pri

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

Solution (Python):
N,M,X = map(int,input().split())
CA = []
ans = 12*(10**5)+1
for n in range(N):
    CA.append(list(map(int,input().split())))

for bit in range(2**N):
    power = [0]*(M+1)
    for n in range(N):
        if bit>>n & 1:
            for i in range(M+1):
                power[i] += CA[n][i]
    rikai = True
    for m in range(M):
        if power[m+1]<X:
            rikai = False
    if rikai:
        ans=min(ans,power[0])
if ans == 12*(10**5)+1:
    ans = -1
print(ans)

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

min_price = float('inf')
for combo in range(0, 2**N):
    combo = list(map(int, bin(combo)[2:]))
    combo = [0] * (N - len(combo)) + combo
    curr_sums = [0] * M
    curr_price = 0
    for i, val in enumerate(combo):
        if val == 1:
            curr_price += books[i][0]
            for j in range(M):
                curr_sums[j] += books[i][j + 1]
    
    good = True
    for val in curr_sums:
        if val < X:
            good = False
    
    if good:
        min_price = min(min_price, curr_price)

print("{}".format('-1' if min_price >= float('inf') else min_price))

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

a = []
c = []

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

INF = 100000000

ans = INF

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

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

min_value = -1
for i in range(2**N):
    sum = [0 for k in range(M+1)]
    for j in range(N):
        if (i >> j) & 1:
            sum = [x+y for x, y in zip(sum, book[j])]
    if min(sum[1:]) >= X and (min_value > sum[0] or min_value == -1):
        min_value = sum[0]

print(min_value)

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

def main():
    N, M, X = map(int, input().split())
    a = np.array([list(map(int, input().split())) for i in range(N)], dtype=int)

    ans = int(1e15)
    for i in range(2**N):
        tmp = np.zeros(M+1, dtype=int)
        for j in range(N):
            if i&1:
                tmp += a[j]
            i >>= 1
        if np.all(tmp[1:] >= X):
            ans = min(ans, tmp[0])
    
    if ans > int(1e9):
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, m, x = list(map(int, input().split()))
lists = []
result_price = 0
existed = False

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

for i in range(1 << n):
  flag = True
  scores = [0] * m
  tmp_price = 0
  for j in range(n):
    if i & (1 << j):
      for k in range(m):
        scores[k] += lists[j][k+1]
      tmp_price += lists[j][0]
  for l in range(m):
    if scores[l] < x:
      flag = False
      break
  if flag and (result_price > tmp_price or result_price == 0):
    existed = True
    result_price = tmp_price
if existed:
  print(result_price)
else:
  print(-1)

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

l=[]
suml=[]
for  i in range(2**n):
  bag=[0]*n
  
  for j in range(n):
    if((i >> j) & 1):
      bag[j]=1
      
  l.append(bag)
  
for bag in l:
  ll=[0]*m
  s=0
  for b in range(len(bag)):
    if bag[b] == 0:
      continue
    
    
    s+=a[b][0]
    for im in range(1, m+1):
      
      ll[im-1] += a[b][im]
      
    if len([i for i in ll if i >= x]) == m:
      suml.append(s)
      

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

Solution (Python):
n, m, x =map(int,input().split())
s = [list(map(int, input().split())) for _ in range(n)]
ans = 10000000
for i in range(2 ** n):
  bag = [0]*(m+1)
  for j in range(n):
    if ((i>>j)&1):
        for _ in range(m+1):
          bag[_] += s[j][_]
  
  if (min(bag[1:]) >= x and ans > bag[0]):
    ans = bag[0]
    
if ans == 10000000:
  print("-1")
else:
  print(ans)

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

yen_min = float('inf')
for bit in range(2 ** n):
    array = []
    for i in range(n):
        if bit>>i & 1:
            array.append(i)
    check = [0]*(m+1)
    for i in array:
        for j in range(m+1):
            check[j] += ca[i][j]
    flag = True
    for i in range(1,m+1):
        if check[i] < x:
            flag = False
    if flag:
        yen_min = min(yen_min, check[0])
if yen_min == float('inf'):
    print(-1)
else:
    print(yen_min)

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

Books = []
for _ in range(N):
    Books.append(list(map(int, input().split())))

ans = 10**9
for i in range(1, N+1):
    for j in combinations(Books, i):
        understand = [0] * M
        cost = 0
        for book in j:
            cost += book[0]
            for p in range(M):
                understand[p] += book[p+1]
        if all(understand[p] >= X for p in range(M)):
            ans = min(ans, cost)

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

Solution (Python):
import sys
n,m,x=map(int,input().split())
A=[]
for i in range(n):
    ca=list(map(int,input().split()))
    A.append(ca)
ans=10**7

for i in range(2**n):
    tmp=[0]*m
    cost=0
    for j in range(n):
        if (1<<j)&i:
            cost+=A[j][0]
            for k in range(m):
                tmp[k]+=A[j][k+1]
    check=True
    for l in range(m):
        if tmp[l]<x:
            check=False
            break
    
    if check:
        ans=min(ans,cost)
                        
if ans==10**7:
    ans=-1
print(ans)

Solution (Python):
import sys
n,m,x=map(int,input().split())
A=[]
for i in range(n):
    ca=list(map(int,input().split()))
    A.append(ca)
ans=10**7

for i in range(2**n):
    tmp=[0]*m
    cost=0
    for j in range(n):
        if (1<<j)&i:
            cost+=A[j][0]
            for k in range(m):
                tmp[k]+=A[j][k+1]
    for l in range(m):
        if tmp[l]<x:
            break
    else:
        ans=min(ans,cost)
if ans==10**7:
    ans=-1
print(ans)

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

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



total_all=[]
for i in range(2**N):
    total=np.zeros(M+1)
    for j in range(N):
        
        
        if ((i >> j) & 1):
            total=total+np.array(clist[j])
    total_all.append(list(total))


ans=[]


for i in range(len(total_all)):
    if min(total_all[i][1:M+1])>=X:
        ans.append(total_all[i][0])

if len(ans)>=1:
    print(int(min(ans)))
else:
    print("-1")

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

ans = 10**9
for i in range(1,n+1):
  for j in combinations(ca, i):
    t = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        t[l] += k[l]
    
    if all(t[a] >= x for a in range(1,m+1)):
      ans = min(ans, t[0])
      
if ans == 10**9:
  print(-1)
else:
  print(ans)

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

A = []
C = []
for c, *a in book:
    C.append(c)
    A.append(a)

ans = float("inf")
for i in range(2 ** n):
    algo = [0] * m
    cost = 0
    for j in range(n):
        if (i >> j) & 1:
            cost += C[j]
            for idx, a in enumerate(A[j]):
                algo[idx] += a
    if all([True if a >= x else False for a in algo]):
        ans = min(ans, cost)

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

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

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

ans =[0]*(m+1)

for i in range(m+1):
    for j in range(n):
        ans[i] = ans[i]+c[j][i]

if min(ans[1:]) < x :
    print(-1)
    exit()

tempans = [0]*(m+1)

for i in range(2 ** n):
    tempans = [0]*(m+1)
    for j in range(n):
        if ((i>>j) & 1):
            for k in range(m+1):
                tempans[k] = tempans[k]+c[j][k]
    if min(tempans[1:]) >= x and tempans[0] < ans[0]:
        ans[0] = tempans[0]

print(ans[0])

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

possible=False
ans=1000000000000000000
for i in range(0,2**N):
    bit=i
    rikai=[]
    cost=0
    for j in range(0,M):
        rikai.append(0)
    for j in range(0,N):
        if bit%2==1:
            cost+=A[j][0]
            for k in range(0,M):
                rikai[k]+=A[j][k+1]
        bit//=2
    sub=True
    for j in range(0,M):
        if(rikai[j]<X):
            sub=False
            break;
    if sub:
        possible=True
        ans=min(ans,cost)

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

Solution (Python):
import math
def fact(n):
    ans = 1
    for i in range(2, n+1):
        ans*= i
    return ans
def comb(n, c):
    return fact(n)//(fact(n-c)*c)

n,m,x = map(int, input().split())
a = []
c = []
for i in range(n):
    arr = list(map(int,input().split()))
    c.append(arr[0])
    a.append(arr[1:])
ans = 123456789
val = 1<<n
for mask in range(val):
    level = [0 for i in range(m)]
    cost = 0
    for i in range(n):
        if((mask>>i)&1):
            cost+=c[i]
            for j in range(m):
                level[j]+=a[i][j]
    ok = True
    for i in range(m):
        if(level[i] < x):
            ok = False
    if(ok):
        ans = min(cost, ans)
if(ans==123456789):
    print(-1)
else:
    print(ans)

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

ans = 1200001
for pat in range(2**n):
    score = [0 for i in range(m)]
    cost = 0
    for i in range(n):
        if pat & (2**i):
            for j in range(m):
                score[j] += a[i][j]
            cost += c[i]
    if cost < ans:
        f = True
        for sc in score:
            if sc < x:
                f = False
                break
        if f:
            ans = cost
if ans == 1200001:
    print(-1)
else:
    print(ans)

Solution (Python):
N,M,X=map(int,input().split())
List = []
for i in range(N):
  List.append(list(map(int, input().split())))
res1= 10000000000000
res2= -1
Flag2 = False

def CheckMaster(a):
  Flag = True
  for i in range(M):
    if a[i] < X:
      Flag = False
    else:
      continue
  return Flag
    
for bits in range(2**N):
  Master=[0]*M
  Money = 0
  for j in range(N):
    if((bits>>j) & 1): 
      Money += List[j][0]
      for k in range(M):
        Master[k] += List[j][k+1]
    if CheckMaster(Master):
      Flag2 = True
      res1 = min(res1,Money) 
    else:  
      pass
if Flag2:
  print(res1)
else:
  print(res2)

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

import numpy as np

def main():
    n, m, x = map(int, input().split())
    c, a = [None]*n, [None]*n
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    
    def dfs(i, cost, A):
        if i == n-1:
            global ans
            if all([ai >= x for ai in A]) and cost < ans:
                ans = cost
            return
        i += 1
        dfs(i, cost, A[:])
        dfs(i, cost+c[i], A[:]+a[i])
    
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    ans = 10**7
    main()

Solution (Python):
import itertools
n, m, x = map(int, input().split())
ca_list = [list(map(int, input().split())) for i in range(n)]
money = []
for j in range(1, n + 1):
    ca_comb = itertools.combinations(ca_list, j)
    for ca_tuple in ca_comb:
        if all([sum([ca[i] for ca in ca_tuple]) >= x for i in range(1, m+1)]):
            money.append(sum([ca[0] for ca in ca_tuple]))
if money:
    print(min(money))
else:
    print(-1)

Solution (Python):
import itertools
n, m, x = list(map(int,input().split()))
c = []
for i in range(n):
    c.append(list(map(int,input().split())))
mn = -1
for bn in itertools.product([0,1], repeat=n):
    money = 0
    skills = [0]*m
    for j in range(n):
        if bn[j] == 1:
            money += c[j][0]
            for k in range(m):
                skills[k] += c[j][k+1]
    if all([y >= x for y in skills]):
        if mn == -1:
            mn = money
        elif money < mn:
            mn = money
print(mn)

Solution (Python):
N,M,X = map(int,input().split())
d=[]
ans = []
for i in range(N):
    l=list(map(int,input().split()))
    d.append(l)
for i in range(2**N):
    u=[0]*M
    price=0
    for j in range(N):
           if ((i>>j) & 1):
                price+=d[j][0]
                for k in range(M):
                    u[k]+=d[j][k+1]
    if all(x>=X for x in u):
        ans.append(price)
print(min(ans) if len(ans) > 0 else -1)

Solution (Python):
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = 10 ** 9 + 7
for l in list(itertools.product([0, 1], repeat=n)):
    cart = [0] * (m + 1)
    for i in [i for i, a in enumerate(l) if a == 1]:
        array = c[i]
        cart = list(map(lambda x,y: x+y, cart, array))
    if min(cart[1::]) >= x:
        ans = min(ans, cart[0])
        
print(ans if ans != 10 ** 9 + 7 else '-1')

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(100000)


def main():
    n, m, x = map(int, input().split())
    cl = [None]*n
    al = [None]*n
    for i in range(n):
        cl[i], *al[i] = map(int, input().split())
    
    def dfs(i, cost, A):
        if i == n-1:
            global ans
            if all([a >= x for a in A]) and cost < ans:
                ans = cost
            return
        i += 1
        dfs(i, cost, A[:])
        dfs(i, cost+cl[i], A[:]+al[i])
    
    dfs(-1, 0, np.array([0]*m))
    
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    ans = 10**7
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,X = inpl()
c = []
a = []
for _ in range(n):
    tmp = inpl()
    c.append(tmp[0])
    a.append(tmp[1:])

res = INF
for fl in itertools.product(range(2), repeat=n):
    ri = [0] * m
    cost = 0
    for i,x in enumerate(fl):
        if x:
            cost += c[i]
            for j,y in enumerate(a[i]):
                ri[j] += y
    if min(ri) >= X:
        res = min(res, cost)
print(res if res != INF 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
    enough=[0]*m 
    money=0
    for sub in bag:
        money+=sub[0]
        for kk in range(1,m+1):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enough[kk-1]+=1
    if 0 not in enough: 
        if ans>money:
            ans=money
if ans==99999999: 
    print(-1)
else:
    print(ans)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(100000)

def main():
    n, m, x = map(int, input().split())
    cl = [None]*n
    al = [None]*n
    total = np.array([0]*m)
    global ans
    ans = 10**7
    for i in range(n):
        c, *a = map(int, input().split())
        a = np.array(a)
        cl[i] = c
        al[i] = a
        total += a
    def dfs(i, cost, A):
        i += 1
        if i == n:
            global ans
            if all([ai >= x for ai in A]) and ans > cost:
                ans = cost
            return
        dfs(i, cost, A[:])
        dfs(i, cost+cl[i], A[:]+al[i])
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    main()

Solution (Python):
def dfs(A):
    if len(A) == n:
        tmp = [0 for i in range(m+1)]
        for i, k in enumerate(A):
            if k:
                for j in range(m+1):
                    tmp[j] += a[i][j]
        chk = 0
        for i in range(1, m+1):
            if tmp[i] >= x:
                chk += 1
        if chk == m:
            ans[0] = min(tmp[0], ans[0])
        return

    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()


n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = [10**10]
dfs([])
if ans[0] != 10**10:
    print(ans[0])
else:
    print(-1)

Solution (Python):
import itertools

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

min_cost = 10 ** 5 * 12 + 1
for i in range(1, n + 1):
    for j in list(itertools.combinations(range(n), i)):
        recog = [0] * m
        cost = 0
        for k in j:
            cost += c[k]
            for l in range(m):
                recog[l] += a[k][l]

        for l in range(m):
            if recog[l] < x:
                break
        else:
            if cost <= min_cost:
                min_cost = cost

if min_cost == 10 ** 5 * 12 + 1:
    print(-1)
else:
    print(min_cost)

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

for i in range(N):
  book_info = list(map(int, input().split()))
  book_price = book_info[0]
  book_effect = book_info[1:]
  book_prices.append(book_price)
  book_effects.append(book_effect)


min_cost = 2**63 - 1 
for comb in range(2**(N)):
  
  cost = 0
  study_effect = []
  
  for study_area in range(M):
    study_effect.append(0)
    
  for pos in range(N):
    
    if (comb&(1<<pos) == (1<<pos)):
      
      cost += book_prices[pos]
      book_effect = book_effects[pos]
      for study_area in range(M):
        study_effect[study_area] += book_effect[study_area]
  
  valid_books = True
  for effect in study_effect:
    if (effect < X):
      valid_books = False
      break
  if (valid_books):
    if (cost < min_cost):
      min_cost = cost

if (min_cost == 2**63 - 1):
  print(-1)
else:
  print(min_cost)

Solution (Python):
n, m, x = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = 10 ** 7

for bit in range(2**n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if (bit >> i) & 1:
            cost += arr[i][0]
            for j in range(m):
                tmp[j] += arr[i][j+1]
    if all(tmp_ >= x for tmp_ in tmp):
        ans = min(ans, cost)

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

Solution (Python):
n, m, x = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = 10 ** 7

for bit in range(2**n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if (bit >> i) & 1:
            cost += arr[i][0]
            for j in range(m):
                tmp[j] += arr[i][j+1]
    for tmp_ in tmp:
        if tmp_ < x:
            break
    else:
        ans = min(ans, cost)

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

Solution (Python):
import itertools
n,m,x=[int(x) for x in input().split()]
book=[]
for i in range(n):
  b=[int(x) for x in input().split()]
  book.append(b)

l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)

price=[]
for i in range(2**n):
  check_list=[0]*(m+1)
  for j in range(n):
    if l[i][j]==1:
      for k in range(m+1):
        check_list[k]+=book[j][k]
  check=[]
  for p in range(1,m+1):
    if check_list[p]<x:
      check.append(False)
  if check==[]:
    price.append(check_list[0])

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

Solution (Python):
import glob
import os
import numpy as np


bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')


REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn


TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def rec(self, N, M, X, now_index, now_knowledge, now_price, books):

        if now_index > N:
            return 12 * 10**5 +1

        next_knowledge = now_knowledge + books[now_index][1:]
        if np.min(next_knowledge) >= X:
            result1 = now_price + books[now_index][0]
        else:
            result1 = self.rec(N, M, X, now_index+1, next_knowledge,  now_price + books[now_index][0], books)

        result2 = self.rec(N, M, X, now_index+1, now_knowledge,  now_price, books)

        if result1 < result2:
            return result1
        else:
            return result2

    def resolve(self):

        N, M, X = map(int, self.input_data().split())

        books = [None]*(N+1)
        for i in range(N):
            books[i+1] = np.array(list(map(int, self.input_data().split())))

        result = self.rec(N, M, X, 1, np.zeros(M), 0, books)
        if result == 12 * 10**5 +1:
            print('-1')
        else:
            print(str(result))


solver = Solver(REL_PATH)
solver.exec_resolve()

Solution (Python):
import numpy as np

N, M, X = list(map(int, input().split()))
a = np.zeros((N, M))
C = np.zeros(N)
for i in range(N):
    tmp = list(map(int, input().split()))
    C[i] += tmp[0]
    a[i] += tmp[1:]
    
answer_price = 10**10

for i in range(1 << N):
    tmp = np.zeros(M)
    cost = 0
    for j in range(N):
        if i % 2 == 1:
            tmp += a[j]
            cost += C[j]
        i = i >> 1

    if all(tmp >= X) and (cost < answer_price):
        answer_price = cost
        
if answer_price == 10**10:
    print("-1")
else:
    print(int(answer_price))