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=[0]*N
A=[]
for i in range(N):
  tmp=list(map(int, input().split()))
  C[i]=tmp[0]
  A.append(tmp[1:])
  
def num2bi(x, k):
  out=format(x, '0'+str(k)+'b')
  return out

cand=[]

tmp=2**N
for i in range(tmp):
  kau=num2bi(i, N)
  nouryoku=[0]*M
  kane=0
  for j in range(N):
    if kau[j]=='1':
      kane+=C[j]
      for k in range(M):
        nouryoku[k]+=A[j][k]
        
  if sum([1 if nouryoku[k]>=X else 0 for k in range(M)])==M:
    cand.append(kane)
    
if len(cand)==0:
  print(-1)
else:
  print(min(cand))

Solution (Python):


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

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

def sum_i(flg, i):
  result = 0
  for j in range(N):
    result += book[j][i]*flg[j]
  return result

def skill(flg):
  if len(flg)==N:
    for i in range(1,M+1):
      if sum_i(flg,i)<X:
        return ('No', -1)
    return ('Yes', sum_i(flg,0))
  else:
    result_0 = skill(flg+[0])
    result_1 = skill(flg+[1])
    if result_0[0]=='No':
      return result_1
    elif result_1[0]=='No':
      return result_0
    else:
      return ('Yes', min(result_0[1],result_1[1]))

print(skill([])[1])

Solution (Python):
N, M, X = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]
cand = []
for i in range(2**N):
    ps = [0] * (M + 1)
    for j in range(N):
        if (i >> j) & 1:
            for idx, x in enumerate(data[j]):
                ps[idx] += x
    if all([x >= X for x in ps[1:]]):
        cand.append(ps[0])
if len(cand) == 0:
    print(-1)
else:
    print(min(cand))

Solution (Python):
from itertools import product

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

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

ans = 100000000
for buylist in product((0, 1), repeat=N):
    cost = 0
    und = [0]*M
    for idx, x in enumerate(buylist):
        if x == 1:
            cost += CA[idx][0]
            for i in range(1, M+1):
                und[i-1] += CA[idx][i]
    cnt = 0
    for i in range(M):
        if und[i] >= X:
            cnt += 1
    if cnt == M and cost < ans:
        ans = cost
if ans == 100000000:
    print(-1)
else:
    print(ans)

Solution (Python):



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




import itertools

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

ans = float('inf')

for case in list(itertools.product('01', repeat=N)):
    val = [0] * M
    price = 0
    
    for j in range(N):
        if case[j]=='1':
            price += data[j][0]
            for m in range(M):
                val[m] += data[j][m+1]

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

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

Solution (Python):
import itertools

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

ans = 10**10
for v in itertools.product([0, 1], repeat=n):
    lst = [0 for i in range(m)]
    money = 0
    for i in range(n):
        if v[i] == 1:
            ci = c[i]
            for j in range(1, m+1):
                lst[j-1] += ci[j]
            money += ci[0]
    if min(lst) >= x:
        ans = min(ans, money)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, X = MAP()
CA = [LIST() for _ in range(N)]
ans = 10**7

for i in range(1<<N):
	i = list("{:b}".format(i).zfill(N))
	cost = 0
	skill = [0]*M
	for j in range(N):
		if i[j] == "1":
			cost += CA[j][0]
			for k in range(M):
				skill[k] += CA[j][k+1]
	if all(x >= X for x in skill):
		ans = min(ans, cost)

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

Solution (Python):
from collections import deque

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


def book_buy_generator():
    for bit_generator in range(1 << N):
        l = [True if bit_generator & (1 << bit) else False for bit in range(N)]
        yield l


big = 10 ** 7
ans = big

for buy in book_buy_generator():
    learn = [0] * M
    cost = 0
    for book_cost, a, bought in zip(C, A, buy):
        if bought:
            cost += book_cost
            for i in range(M):
                learn[i] += a[i]

    learn_ok = True
    for algorithm in learn:
        if algorithm < X:
            learn_ok = False

    if learn_ok:
        ans = min(ans, cost)

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

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

ans_init = 10 ** 8
ans = ans_init
for i in range(2 ** n):
    temp_list = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            temp_list = [t + b for t, b in zip(temp_list, b_list[j])]
    
    if min(temp_list[1:m+1]) >= x and temp_list[0] < ans:
        ans = temp_list[0]
print(ans if ans != ans_init else -1)

Solution (Python):


from itertools import combinations



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

    COSTS = []
    for n in range(N):
        for c in combinations(CA, n+1):
            SUM = [0 for _ in range(M)]
            COST = 0
            for ca in c:
                COST += ca[0]
                for m in range(M):
                    SUM[m] += ca[m+1]
            if all(list(map(lambda x: x >= X, SUM))):
                COSTS.append(COST)
    if COSTS:
        print(min(COSTS))
        return
    print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
n,m,x=map(int,input().split())
from itertools import product
li=[]
ans=10**9
for i in range(n):
    a=list(map(int,input().split()))
    li.append(a)
for p in product([0, 1], repeat = n):
    cnt = [0 for _ in range(m)]
    price=0
    for i in range(n):
        if p[i]==1:
            price+=li[i][0]
            for j in range(m):
                cnt[j]+=li[i][j+1]
    if min(cnt)>=x:
        ans=min(ans,price)
if ans==10**9:
    print("-1")
else:
    print(ans)

Solution (Python):
N, M, X = map(int, input().split())
C, A = [], []
ans = 1200000
exist = False
for n in range(N):
    li = list(map(int, input().split()))
    C.append(li[0])
    A.append(li[1:])
for b in range(1 << N):
    amount = 0
    understand = [0] * M
    for n in range(N):
        if (b >> n) & 1 == 1:
            amount += C[n]
            for m in range(M):
                understand[m] += A[n][m]
    achieve = True
    for m in range(M):
        if X > understand[m]:
            achieve = False
    if achieve:
        exist = True
        ans = min(ans, amount)
if exist:
    print(ans)
else:
    print(-1)

Solution (Python):

from itertools import combinations, combinations_with_replacement, product, permutations


import sys

buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, X, CA):
    A = [ca[1:] for ca in CA]
    C = [ca[0] for ca in CA]
    ans = INF
    for k in range(1, N+1):
        for i in combinations(range(N), r=k):
            m = [0] * M
            t = 0
            for j in i:
                for k, a in enumerate(A[j]):
                    m[k] += a
                t += C[j]
            if min(m) >= X:
                ans = min(ans, t)
    if ans == INF:
        ans = -1
    return ans


def main():
    N, M, X = read_int_n()
    CA = [read_int_n() for _ in range(N)]
    print(slv(N, M, X, CA))


if __name__ == '__main__':
    main()

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

    Alg = [0]*M
    cost = 0
    for a in A:
        cost += a[0]
        for i in range(M):
            Alg[i] += a[i+1]
    for i in range(M):
        if Alg[i] < X:
            print(-1)
            return

    ans = cost
    for P in product( range(2), repeat=N):
        Alg = [0]*M
        cost = 0
        for i in range(N):
            if P[i] == 0:
                continue
            cost += A[i][0]
            for j in range(M):
                Alg[j] += A[i][j+1]
        check = True
        for i in range(M):
            if Alg[i] < X:
                check = False
                break
        if check:
            if cost < ans:
                ans = cost
    print(ans)
        
if __name__ == '__main__':
    main()

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
 
n,m,x = LI()
a = [LI() for i in range(n)]
result = 12000000
for i in range(1 << n):
    c = 0
    val = [0]*m
    for j in range(n):
        if(i & (1 << j)):
            c += a[j][0]
            for k in range(m):
                val[k] += a[j][k+1]
    f = True
    for j in range(m):
        if(val[j] < x):
            f = False
            break
    
    if(f):
        if(result > c):
            result = c

if(result == 12000000):
    print(-1)
else:
    print(result)

Solution (Python):
import itertools

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

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


ans=1000000000
for bit in itertools.product([0,1],repeat=n):
  b=[0]*m
  cost=0
  for i in range(n):
    if bit[i]:
      cost+=book[i][0]
      for j in range(1,m+1):
        b[j-1]+=book[i][j]
  k=1
  for i in range(m):
    if b[i]<x:
      k=0
      break
  if k:
    ans=min(ans,cost)
    
if ans==1000000000:
  print(-1)
else:
  print(ans)

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

a = [[0 for j in range(m)] for i in range(n)]
cost = [0 for j in range(n)]

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

best_cost = sum(cost) + 1



for mask in range(2**n):
	mm = mask
	knowledge = [0 for i in range(m)]
	total_cost = 0
	book_number = 0 
	
	while mask > 0:
		
		if (mask % 2) == 1:
			total_cost += cost[book_number]
			for j in range(m):
				knowledge[j] += a[book_number][j]

		mask = mask // 2
		book_number += 1

	

	ok = True
	for j in range(m):
		if knowledge[j] < x:
			ok = False 
			break

	if ok:
		
		best_cost = min(best_cost, total_cost)

if best_cost < sum(cost) + 1:
	print(best_cost)
else:
	print(-1)

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

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:])
A = np.array(A)

ans = sum(C)
flag = False

for i in range(1, N+1):
    for c in combinations(range(N), i):
        k = np.zeros(M)
        cost = 0
        for n in c:
            k += A[n]
            cost += C[n]
        if np.all(k >= X):
            flag = True
            ans = min(ans, cost)

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

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


N,M,K = m()
po = []
for i in range(N):
    po.append(l())

ans = Max

for i in range(2**N):
    kane = 0
    un = [0 for _ in range(M)]
    no = i
    for j in range(N):
        ppp = no % 2
        if ppp:
            for k in range(M+1):
                if k == 0:
                    kane += po[j][k]
                else:
                    un[k-1] += po[j][k]
        no //=2
    if all(map(lambda x:x >= K,un)):
        ans = min(ans,kane)
if ans != Max:
    print(ans)
else:
    print(-1)

Solution (Python):

N, M, X = map(int, input().split())
prices = []
effects = []
for _ in range(N):
	values = list(map(int, input().split()))
	prices.append(values[0])
	effects.append(values[1:])

sum_price = sum(prices)
min_price = sum_price + 1

for n in range(2 ** N):
	price = 0
	understood = [0] * M
	i = 0
	while n > 0:
		if n % 2 == 1:
			price += prices[i]
			for j in range(M):
				understood[j] += effects[i][j]
		i += 1
		n //= 2
	if all(understood[j] >= X for j in range(M)):
		if price < min_price:
			min_price = price

if min_price > sum_price:
	print(-1)
else:
	print(min_price)

Solution (Python):
import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M, X = map(int,readline().split())
ca = np.array([list(map(int, readline().split())) for _ in range(N)])




ans = pow(10, 9) + 7

flag = False
for bit in range(0, 1<<N):
    acc = 0
    count = np.zeros(M)
    for i in range(N):
        if bit & (1<<i):
            ca_ = ca[i]
            acc += ca_[0]
            count += ca_[1:]
    if count.min() >= X:
        ans = min(ans, acc)
        flag = True
    
print(ans) if flag else print(-1)

Solution (Python):
def bit_all(x):
    price = 0
    ret = [0] * M
    b = str(format(x, "012b"))
    for i in range(N):
        if b[- (i + 1)] == "1": 
            for j in range(M):
                ret[j] += A[i][j]
            price += C[i]
            
    return price, ret

N, M, X = list(map(int,input().split()))
C = []
A = []
for i in range(N):
    input_ = list(map(int,input().split()))
    C.append(input_[0])
    A.append(input_[1 : M + 1])
    
ans = 10 ** 9 + 7
for x in range(2 ** N):
    price, ret = bit_all(x)
    if min(ret) >= X:
        ans = min(price, ans)

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

Solution (Python):
import sys
input = sys.stdin.readline
n,m,x = map(int,input().split())
clist = []
alist = []
ans = 10**20
for i in range(n):
    ca = list(map(int,input().split()))
    c = ca[0]
    a = ca[1:]
    clist.append(c)
    alist.append(a)

for i in range(2**n):
    y = 0
    rikai = [0]*m
    bi = bin(i)[2:].zfill(n)
    for j in range(n):
        if bi[j] == '1':
            y += clist[j]
            for k in range(m):
                rikai[k] += alist[j][k]
    for j in range(m):
        if rikai[j] < x:
            break
    else:
        ans = min(ans,y)
if ans == 10**20:
    print(-1)
else:
    print(ans)

Solution (Python):

import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache

readline=sys.stdin.readline
sys.setrecursionlimit(2000000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)


def main():
    N,M,X=list(map(int,input().split()))
    C=[]
    A=[]
    for a in range(N):
        tmp=list(map(int,input().split()))
        C.append(tmp[0])
        A.append(tmp[1:])
    ans=inf
    for a in range(1<<N):
        B=bin_(a,N)
        rikai=[0]*M
        cost=0
        for b in range(N):
            if B[b]==1:
                cost+=C[b]*B[b]
                for c in range(M):
                    rikai[c]+=A[b][c]
        if min(rikai)>=X:
            ans=min(ans,cost)
    if ans==inf:
        print(-1)
    else:
        print(ans)


main()

Solution (Python):

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

ans = 10**1000
for i in range(2**N):
    prc = 0
    li = [0 for _ in range(M)]
    for j in range(N):
        if (i>>j)&1:
            prc += A[j][0]
            for k in range(M):
                li[k] += A[j][k+1]
    
    for k in range(M):
        if li[k]<X:
            break
    else:
        ans = min(prc,ans)
if ans == 10**1000:
    print(-1)
else:
    print(ans)

Solution (Python):
INF=float("inf")
n, m, x = map(int, input().strip().split())
L = [list(map(int, input().split())) for _ in range(n)]

ans=INF
for i in range(2**n):
    bin_=i
    money=0
    rikaido=[0]*m
    book=0
    while bin_:
        if bin_ & 1: 
            money+=L[book][0]
            for j in range(m):
                rikaido[j]+=L[book][j+1]
        bin_>>=1
        book+=1
    for j in range(m):
        if rikaido[j]<x:
            break
    else:
        ans=min(ans,money)
        
if ans==INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import itertools
N,M,X = map(int,input().split())
A = []
for i in range(N):
    a = list(map(int,input().split()))
    A.append(a)
ans = 10 ** 10
Z = [0,1]
Y = list(itertools.product(Z,repeat=N))
for y in Y:
    tmp = [0 for i in range(M)]
    ctmp = 0
    for i in range(N):
        if y[i] == 1:
            ctmp += A[i][0]
            for j in range(M):
                tmp[j] += A[i][j+1]
    check = 0
    for k in tmp:
        if k < X:
            check = 1
    if check == 0:
        if ctmp < ans:
            ans = ctmp
if ans == 10 ** 10:
    ans = -1
print(ans)

Solution (Python):

import sys

def main():
    N, M, X = map(int, input().split())
    C = [None] * N
    A = [None for _ in range(N)]
    for i in range(N):
        C[i], *A[i] = map(int, input().split())
    
    
    ans = 10**12
    for i in range(2**N):
        tmp = [0] * M
        tmpC = 0
        for j in range(N):
            if (i >> j) & 1:
                for k in range(M):
                    tmp[k] += A[j][k]
                tmpC += C[j]
        flag = True
        for k in range(M):
            if tmp[k] < X:
                flag = False
                break
        if flag:
            ans = min(ans, tmpC)
    
    if ans == 10**12:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

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

res = 10 ** 9
for i in range(2 ** N):
    c = 0
    s = [0 for _ in range(M)]
    for j in range(N):
        if i & (2 ** j):
            c += C[j]
            for k in range(M):
                s[k] += L[j][k]
    f = 1
    for j in range(M):
        if s[j] < X:
            f = 0
            break
    if f:
        res = min(res, c)

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

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


def submit():
    n, m, x = map(int, input().split())
    books = {}
    for i in range(n):
        e = list(map(int, input().split()))
        c = e[0]
        books[i] = (c, np.array(e[1:]))

    min_cost = float("inf")
    for pt in product([0, 1], repeat=n):
        curr_cost = 0
        curr_skills = np.zeros(m)
        for i, isbuy in enumerate(pt):
            if isbuy: 
                cost, skills = books[i]
                curr_cost += cost
                curr_skills += skills

            if np.all(curr_skills >= x) and curr_cost < min_cost:
                min_cost = curr_cost

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


submit()

Solution (Python):
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy




def main():
    N,M,X = map(int, input().split())
    ca = []
    res = sys.maxsize
    for _ in range(N):
        ca.append(list(map(int, input().split())))
    for i in range(2 ** N):
        tmp = [0]*M
        tmpres = 0
        for j in range(N):
            if ((i >> j) & 1):
                tca = ca[N-1-j]
                tmpres += tca[0]
                for k in range(M):
                    tmp[k] += tca[1+k]
        tassei = True
        for a in tmp:
            if a < X:
                tassei = False
                break
        if tassei:
            res = min(res,tmpres)
    if res != sys.maxsize:
        print(res)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):

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

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

for i in range(M):
    x = sum([a[i] for a in A])
    if x < X:
        print(-1)
        exit()


ans = float('inf')
def solve(buf):
    global ans

    if len(buf) == N:
        can_solve = True
        for i in range(M):
            x = sum([A[j][i] for j in range(N) if buf[j]])
            if x < X:
                can_solve = False
                break

        if can_solve:
            c =  sum([C[j] for j in range(N) if buf[j]])
            ans = min(ans, c)

    else:
        solve(buf + [0])
        solve(buf + [1])


solve([])
print(ans)

Solution (Python):
N, M, X = map(int, input().split())  
books = [list(map(int, input().split())) for _ in range(N)]
ans = float("inf")
for mask in range(1 << N):  
    binary = []
    for i in range(N):
        binary.append((mask >> i) & 1)
    
    tmp_cost = 0
    now_understand = [0]*M
    for i in range(N):
        if binary[i] == 1:
            c, *A = books[i]
            tmp_cost += c
            for j in range(len(A)):
                now_understand[j] += A[j]

    flag = True
    for i in range(M):
        if now_understand[i] < X:
            flag = False

    if flag:
        ans = min(ans, tmp_cost)

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

Solution (Python):
import itertools
n,m,x=map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(n)]
P = list(itertools.product([0,1], repeat=n))

MIN=10000000000
for p in P:
    ans = 0
    now = [0]*m
    for i in range(n):
        if p[i]==1:
            ans += ca[i][0]
            for g in range(1,m+1):
                now[g-1] += ca[i][g]
    frag = True
    for i in range(m):
        if now[i]<x:
            frag = False
            break
    if frag:
        MIN = min(ans,MIN)

if MIN == 10000000000:
    print(-1)
else:
    print(MIN)

Solution (Python):
import numpy as np
n,m,x = map(int,input().split())
c = []
for i in range(n):
  a = [int(i) for i in input().split()]
  c.append(a)
  
c = np.array(c)
ans = float('inf')
for i in range(1,2**n):
  chk = [0]*m
  cost = 0
  for j in range(n):
    if (i>>j)&1 == 1:
      cost += c[j][0]
      chk += c[j][1:]
  if min(chk) >= x:
    ans = min(ans,cost)
  
if ans == float('inf'):
  ans = -1
print(ans)

Solution (Python):
import itertools
import numpy as np

N,M,X = map(int, input().split())
arr = np.array([list(map(int, input().split())) for _ in range(N)])
und=[0]*M
c_max = 10**7

for i in range(N):
    lis=list(itertools.combinations(arr,i+1))
    for li in lis:
        c=0
        a=np.array([0]*M)
        for l in li:
            c += l[0]
            a += l[1:]
        
        if np.all(a>=X) and c<c_max:
            c_max=c
if c_max < 10**7:
    print(c_max)
else:
    print('-1')

Solution (Python):
import numpy as np

n,m,x = map(int, input().split())
c = []
a = []
s =  np.zeros(m)
for i in range(n):
    temp = list(map(int, input().split()))
    c.append(temp[0])
    a.append(temp[1:])
    s+=np.array(temp[1:])

a = np.array(a)

if (min(s) < x):
    print(-1)
else:
    ans = np.inf
    for i in range(0, 2 ** n):
        ct = bin(i)[2:].zfill(n)
        price = 0
        score = np.zeros(m)
        for j in range(n):
            score += int(ct[j]) * a[j]
            price += int(ct[j]) * c[j]
        if (min(score) >= x):
            ans = min(price,ans)
    print(ans)

Solution (Python):


import itertools
import sys


INF = sys.maxsize // 10


def all_subsets(xs):
    n = len(xs)
    gs = (itertools.combinations(xs, i) for i in range(n + 1))
    return itertools.chain(*gs)


def optimize(n, m, x, cs, table):
    res = INF
    for book_ids in all_subsets(list(range(n))):
        unds = [0 for _ in range(m)]
        cost = 0
        for book_id in book_ids:
            cost += cs[book_id]
            for j, a in enumerate(table[book_id]):
                unds[j] += a
        if all(und >= x for und in unds):
            res = min(res, cost)
    return res


def main():
    n, m, x = (int(z) for z in input().split())
    cs = [0 for _ in range(n)]
    table = [None for _ in range(n)]
    for i in range(n):
        ys = [int(z) for z in input().split()]
        cs[i] = ys[0]
        table[i] = ys[1:][:]
    res = optimize(n, m, x, cs, table)
    if res < INF:
        print(res)
    else:
        print(-1)


if __name__ == '__main__':
    main()