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


from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M, X = mulinputs()
    datas = []
    check = [0] * M
    for _ in range(N):
        tmp = list(mulinputs())
        datas.append(tmp)
        for i in range(1,M+1):
            check[i-1] += tmp[i]
    for c in check:
        if c < X:
            print(-1)
            exit()

    min_value = INF
    for b in range(1<<N):
        tmp = b
        total = 0
        idx = 0
        check = [0] * M
        while tmp > 0:
            if tmp%2==1:
                total += datas[idx][0]
                for m in range(1, M+1):
                    check[m-1] += datas[idx][m]
            tmp >>=1
            idx += 1
        if len(check) == len(list(filter(lambda x: x >= X, check))):
            min_value = min(total, min_value)


    
    print(min_value)

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




import numpy as np


def main():
    n, m, x = map(int, input().split())
    books = [np.array(list(map(int, input().split()))) for _ in range(n)]
    ans = INF
    for bit in range(1 << n):
        bag = [0] * n
        for i in range(n):
            if bit >> i & 1:
                bag[i] = 1
        tmp = np.array([0] * m)
        cost = 0
        for i, v in enumerate(bag):
            if v:
                cost += books[i][0]
                tmp += books[i][1:]
        if all([i >= x for i in tmp]):
            ans = min(ans, cost)
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, M, X = map(int, input().split())
items = []
for _ in range(N):
    tmps = list(map(int, input().split()))
    price = tmps[0]
    l = tmps[1:]
    items.append((price, l))
n = len(items)
patterns = []

for i in range(2 ** n):
    bag = []
    for j in range(n):  
        if ((i >> j) & 1):  
            bag.append(items[j])  
    patterns.append(bag)

ans = 100000000000
for pattern in patterns:
    sum_price = 0
    sum_l = [0 for _ in range(M)]
    for price, l in pattern:
        sum_price += price
        for i in range(M):
            sum_l[i] += l[i]
    check = True
    for i in range(M):
        if sum_l[i] < X:
            check = False
    if check:
        ans = min(ans, sum_price)

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

Solution (Python):




geta = lambda fn: list(map(fn, input().split()))

N, M, X = geta(int)
b = []
for _ in range(N):
    b.append(geta(int))

inf = 10**7

ans = inf

for c in range(0, 2**N):
    tmp = c
    cost = 0
    bi = 0
    sk = [0] * M
    while tmp > 0:
        if tmp & 1 == 1:
            cost += b[bi][0]
            for i in range(M):
                sk[i] += b[bi][i + 1]

        tmp = tmp >> 1
        bi += 1

    if min(sk) >= X and ans > cost:
        ans = cost

print(ans if ans < inf else -1)

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

num = 2**n
mon = 10**18

for i in range(num):
    tmp = format(i, '0'+str(n)+'b')
    
    tmp_mon = 0
    alg = [0]*(m)
    for j in range(n):
        if int(tmp[j]) == 1:
            for k in range(m):
                alg[k] += ca[j][1+k]
            tmp_mon += ca[j][0]
    
    flag = True
    
    for j in range(m):
        if alg[j] < x:
            flag = False
            break
    
    if flag == False:
        continue
    
    mon = min(tmp_mon,mon)

if mon == 10**18:
    print(-1)
else:
    print(mon)

Solution (Python):
N, M, X = map(int, input().split())
matrix = tuple(tuple(map(int, input().split())) for _ in range(N))
ans = float("inf")
for comb in range(1 << N):
    temp = [0] * (M + 1)
    for i in range(N):
        if comb & (1 << i):
            for m in range(M + 1):
                temp[m] += matrix[i][m]
    if all(temp[i] >= X for i in range(1, M + 1)):
        ans = min(ans, temp[0])
print(-1 if ans == float("inf") else ans)

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

c = []
a = []

for i in range(n):
    ai = list(map(int,input().split()))
    ci = ai.pop(0)
    a.append(ai)
    c.append(ci)

for j in range(m):
    tmp = 0
    for i in range(n):
        tmp += a[i][j]
    if tmp<x:
        print(-1)
        exit()

def dps(lis, num):
    if num == n:
        res = 0
        for j in range(m):
            tmp = 0
            for i in lis:
                tmp += a[i][j]
            if tmp < x:
                return 10000000
        for i in lis:
            res += c[i]
        return res
    else:
        lisnext = lis + [num]
        return min(dps(lisnext,num+1),dps(lis,num+1))

print(dps([],0))

Solution (Python):
from itertools import product
n, m, x = list(map(int, input().split()))
cl = [0] * n
al = [[]*m for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    cl[i] = tmp[0]
    al[i] = tmp[1:]


def dfs(status, book):
    for i in range(m):
        status[i] += book[i]
    return status


ans = 10**10
for bit in product([0, 1], repeat=n):
    
    status = [0]*m
    money = 0
    for i, b in enumerate(list(bit)):
        if b == 1:
            for k in range(m):
                status[k] += al[i][k]
            money += cl[i]
    flag = True
    for i in range(m):
        if status[i] >= x:
            continue
        else:
            flag = False
    if flag:
        ans = min(ans, money)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Solution (Python):
INF = 10**13
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    CA = list(map(int, input().split()))
    C += [CA[0]]
    A += [CA[1:]]
ans = INF
for b in range(2**N):
    tmpA = [0] * M
    cost = 0
    for i in range(N):
        if (b >> i) & 1:
            cost += C[i]
            for ii, ai in enumerate(A[i]):
                tmpA[ii] += ai
    flag = True
    for ai in tmpA:
        if ai >= X:
            continue
        flag = False
        break
    if flag:
        ans = min(ans, cost)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
def main():
    N, M, X = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]
    
    total_cost = 1e10
    possible = False
    for i in range(2**N):
        tmp_cost = 0
        rikai = [0]*M
        for j in range(N):
            if ((i >> j) & 1):
                
                tmp_cost += A[j][0]
                for k in range(M):
                    rikai[k] += A[j][k+1]
        
        if min(rikai) >= X:
            possible = True
            total_cost = min(total_cost, tmp_cost)
    
    if possible:
        print(total_cost)
    else:
        print(-1)


if __name__ == '__main__':
    main()

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

c = [0] * n
a = [[0] * m for _ in range(n)]

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

ans = float("inf")
for mask in range(1 << n):
    sum = 0
    skill = [0] * m
    for j in range(n):
        if (mask >> j) & 1 == 1:
            for k in range(m):
                skill[k] += a[j][k]
            sum += c[j]

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

    if flag is True:
        ans = min(ans, sum)

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

Solution (Python):
N,M,X = map(int,input().split(" "))
A = []
lis = []
rikai = [[0 for _ in range(M)]for _ in range(2 ** N)]
flag = True
kane = 0
ans = 10 ** 10
for i in range(N):
    A.append(list(map(int,input().split(" "))))
    
for i in range(2 ** N):
    lis.clear()
    kane = 0
    flag = True
    for i2 in range(N):
        if ((i >> i2) & 1):
            lis.append(i2)
    for i2 in lis:
        kane += A[i2][0]
        for i3 in range(M):
            rikai[i][i3] += A[i2][i3 + 1]
    for i2 in rikai[i]:
        if i2 < X:
            flag = False
    if flag:
        if ans > kane:
            ans = kane
            
if ans != 10 ** 10:
    print(ans)
else:
    print(-1)

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

ans=10**8
for mask in range(1,1<<n):
    mem=[0]*m
    c=0
    for i in range(n):
        if (mask & (1<<i)):
            c+=book[i+1][0]
            for j in range(m):
                mem[j]+=book[i+1][j+1]
    for j in range(m):
        if mem[j]<x:
            break
    else:
        ans=min(ans,c)
if ans==10**8:
    print(-1)
else:
    print(ans)

Solution (Python):
n,m,x = map(int, input().split())
c = [0 for i in range(n)]
a = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    for j in range(m):
        a[i][j] = tmp[j + 1]
able = False
ans = 10**8
for i in range(2**n):
    price = 0
    flag = True
    buy = [0 for j in range(n)]
    rikai = [0 for j in range(m)]
    for j in range(n):
        if i>>j & 1 == 1:buy[j] = 1
    for j in range(n):
        if buy[j] == 1:
            price += c[j]
            for k in range(m):
                rikai[k] += a[j][k]
    for j in range(m):
        if rikai[j] < x:
            flag = False
            break
    if not flag:continue
    able = True
    ans = min(ans,price)
if able:print(ans)
else:print(-1)

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

CA = []
for i in range(N):
    CA.append(list(map(int, input().split())))
    
ans = 10**10
flag = False
for i in range(2 ** N):
    purchase = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            purchase[N - 1 - j] = 1
    money = 0
    skill = [0] * M
    for j in range(N):
        if purchase[j] == 1:
            money += CA[j][0]
            for k in range(1, M+1):
                skill[k-1] += CA[j][k]
    if min(skill) >= X:
        ans = min(ans, money)
        flag = True

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

Solution (Python):

n,m,x = map(int,input().split())
c=[0 for _ in range(n)]
a=[[] for j in range(n)]



maxcnt = 10**9+7
for i in range(n):
	k = list(map(int,input().split()))
	c[i] = k[0]
	a[i] = k[1:]
for i in range(2**n):
	asum = [0 for _ in range(m)]
	cnt = 0
	for j in range(n):
		if ((i>>j) & 1):
			cnt += c[j]
			for k in range(m):
				asum[k] += a[j][k]
	cntj = 0
	for k in range(m):
		if asum[k] >= x:
			cntj += 1
	if cntj == m:
		if cnt <= maxcnt:
			maxcnt = cnt

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

Solution (Python):

import numpy as np
from collections import deque
import collections

n, m, x = list(map(int, input().split()))
c = [0] * n
A = [[]] * n
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    A[i] = tmp[1:]
A = np.array(A)

ok_flg = False

for i in range(2 ** n):
    money = 0
    skills = np.zeros(m)

    for j in range(n):
        if ((i >> j) & 1):
            money += c[j]
            skills = skills + A[j]
    if (np.all(skills >= x) and ok_flg):
        ans = min(ans, money)
    if(np.all(skills >= x) and (not ok_flg)):
        ok_flg = True
        ans = money

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

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


ans = 10**10
for bit in range(1<<n):
    s = [0]*m
    now = 0
    for i in range(n):
        if bit & 1<<i:
            for j in range(m):
                s[j] += C[i][j+1]
            now += C[i][0]
    if all(y >= x for y in s):
        
        ans = min(ans,now)
if ans == 10**10:
    print(-1)
    exit()
print(ans)

Solution (Python):
N, M, X = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
b = 2 ** N
minima = int(1e18)
flg = False
for i in range(b):
  S = 0
  L = [0 for _ in range(N)]
  SS = [0 for _ in range(M)]
  tmp = i
  for j in range(N):
    if tmp % 2 == 1:
      L[j] = 1
    tmp //= 2
  for k in range(N):
    if L[k] == 1:
      S += A[k][0]
      for l in range(M):
        SS[l] += A[k][l+1]
  if min(SS) >= X:
    flg = True
    if minima > S:
      minima = S
if flg:
  print(minima)
else:
  print(-1)

Solution (Python):
n, m, x = map(int, input().split())
ca = [[int(i) for i in input().split()] for _ in range(n)]
y = []
for b in [[i >> j & 1 for j in range(n)] for i in range(2**n)]:
    xi = [0] * m
    yi = 0
    for j, bj in enumerate(b):
        if bj == 0:
            continue
        yi += ca[j][0]
        for k in range(m):
            xi[k] += ca[j][k + 1]
    if min(xi) >= x:
        y.append(yi)
if y:
    print(min(y))
else:
    print(-1)

Solution (Python):
from itertools import *
n,m,x=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(n)]
a=10**7
for i in range(1,n+1):
    for j in combinations(L,i):
        b=[0]*(m+1)
        for k in j:
            b=[b[i]+k[i] for i in range(m+1)]
        if all(i>=x for i in b[1:]):
            a=min(a,b[0])
print(-1 if a==10**7 else a)

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

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

ans = 10**7

for i in range(2**N):
  bit = format(i, "0" + str(N) +'b')
  skill = [0]*M
  cost = 0
  for j in range(N):
    if bit[j] == "1":
      cost += C[j][0]
      for s in range(M):
        skill[s] += C[j][s+1]

  tmp = 0
  for j in range(M):
    if skill[j] >= X:
      tmp += 1
    else:
      break
  
  if tmp == M:
    ans = min(ans,cost)
  
  




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

else:
  print(ans)

Solution (Python):
from itertools import product

n, m, x = map(int, input().split())
cas = [tuple(map(int, input().split())) for _ in range(n)]
ans = 10 ** 20

for elem in product(range(2), repeat=n):
    buy_rep = [0] * (m + 1)
    for i in range(n):
        if elem[i]:
            for j in range(1, m + 1):
                buy_rep[j] += cas[i][j]
            buy_rep[0] += cas[i][0]
    if m == len(list(filter(lambda y: x <= y, buy_rep[1:]))):
        ans = min(ans, buy_rep[0])
if ans == 10 ** 20:
    print(-1)
else:
    print(ans)

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

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

INF = float('inf')
ans = INF

for i in range(1,2**N):
  skill = [0 for i in range(M)]
  b = 0
  for j in range(N):
    if(i>>j)&1==1:
      b += L[j][0]
      for t in range(M):
        skill[t] += L[j][t+1]
  if all([skill[y] >= X for y in range(M)]):
    
    ans = min(ans,b)

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

Solution (Python):
def c_skill_up():
    N, M, X = [int(i) for i in input().split()]
    Algo = [[int(i) for i in input().split()] for j in range(N)]
    ans = float('inf')
    for bits in range(1, 1 << N):
        select = []
        for d in range(N):
            if (bits >> d) & 1 == 1:
                select.append(d)

        understanding = [0] * M
        tmp = 0
        for i in select:
            c, *a = Algo[i]
            tmp += c
            for k, p in enumerate(a):
                understanding[k] += p
        if len([1 for u in understanding if u >= X]) == M:
            ans = min(ans, tmp)
    return ans if ans != float('inf') else -1

print(c_skill_up())

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,x = LI()
    s = LIR(n)
    ans = float("inf")
    for b in range(1<<n):
        cost = 0
        k = [0]*m
        for i in range(n):
            if b&(1<<i):
                cost += s[i][0]
                for j in range(m):
                    k[j] += s[i][j+1]
        if cost < ans and all([i >= x for i in k]):
            ans = cost
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
N, M, X = map(int, input().split())
p = []
c = []
for i in range(N):
    new = [int(j) for j in input().split()]
    p.append(new[0])
    c.append(new[1:])
    
flag = 0
total = [0]*M
for i in range(N):
    for j in range(M):
        total[j] += c[i][j]

for j in range(M):
    if total[j] < X:
        flag = 1
        
if flag == 1:
    print(-1)
else:
    minimum = sum(p)
    for k in range(2**N):
        total = [0]*M
        total_p = 0
        for i in range(N):
            if ((k >> i) & 1):
                total_p += p[i]           
                for j in range(M):
                    total[j] += c[i][j]
            flag2 = 0
            for j in range(M):
                if total[j] < X:
                    flag2 = 1
            if flag2==0:
                if total_p < minimum:
                    
                    minimum=total_p
    print(minimum)

Solution (Python):
from itertools import product

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

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

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

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read


sys.setrecursionlimit(10**7)

from itertools import combinations, product

import numpy as np
def run():
    N,M,X = map(int, sysread().split())
    C = []
    A = []
    for _ in range(N):
        c, *a = map(int, sysread().split())
        C.append(c)
        A.append(a)
    A = np.array(A)
    C = np.array(C)
    val = float('inf')
    for buy in product((0,1), repeat=N):
        buy = np.array(list(buy))
        cost = (C * buy).sum()
        prog = (A.T * buy).sum(axis=1)
        if np.all(prog >= X):
            val = min(val, cost)
    if val == float('inf'):
        print(-1)
        return None
    print(val)


if __name__ == "__main__":
    run()

Solution (Python):
import itertools

N,M,X = map(int, raw_input().split())
Data = [map(int, raw_input().split()) for _ in range(N)]
C = [itertools.combinations(Data, i) for i in range(N+1)]
ans = -1
for c in itertools.chain.from_iterable(C):
    
    T = [0]*(M+1)
    for a in c:
        for i,b in enumerate(a):
            T[i] += b
    
    ok = True
    for t in T[1:]:
        if t < X:
            ok = False
            break

    if ok:
        price = T[0]
        
        if ans == -1:
            ans = 100000000
        ans = min(ans, price)

print ans

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

for i in range(2 ** n):
    check = [0] * n

    for j in range(n):
        if ((i >> j) & 1):
            check[n - 1 - j] = 1

    total = 0
    skill = [0] * m
    for k in range(n):
        if check[k] == 0:
            continue
        total += li[k][0]

        for l in range(m):
            skill[l] += li[k][l+1]

    skill.sort()
    if skill[0] >= x:
        ans = min(ans,total)

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

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

n, m, x = map(int, input().split())
c = []
a = np.empty((n, m), dtype='i8')
for i in range(n):
    ipt = list(map(int, input().split()))
    c.append(ipt[0])
    a[i] = ipt[1:]

can = False
res = maxsize
for pt in product(range(2), repeat=n):
    understanding = np.zeros(m, dtype='i8')
    price = 0
    for i, b in enumerate(pt):
        if b:
            understanding += a[i]
            price += c[i]

    if np.all(understanding >= x):
        can = True
        if price < res:
            res = price

print(res) if can else print(-1)

Solution (Python):



from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy
N, M, X = [int(_) for _ in input().split()]
CA = [[int(_) for _ in input().split()] for i in range(N)]

ret = []

def dfs(index, rikaido, cost):
    
    global ret
    rikaido = [rikai + rikaido[i] for i, rikai in enumerate(CA[index][1:])]
    cost += CA[index][0]

    if all([i >= X for i in rikaido]):
        ret += [cost]
        return
    
    for i in range(index+1, N):
        dfs(i, copy.copy(rikaido), cost)

for i in range(N):
    dfs(i, [0] * M, 0)

if not ret:
    print(-1)
else:
    print(min(ret))

Solution (Python):




import itertools  
import numpy as np
def LI():
    return (map(int,input().split()))

n,m,x=LI()
c=[]
a=[]
for i in range(n):
    ct,*at=LI()
    c.append(ct)
    a.append(at)
    
a=np.array(a)

ans=10**15
rrr=list(itertools.product((0,1),repeat=n))

for i in rrr:
    tmp=np.array([0]*m)
    cost=0
    for j,k in enumerate(i):
        if k==1:
            tmp+=a[j]
            cost+=c[j]
        if all(tmp>=x):
            ans=min(ans,cost)
if ans==10**15:
    ans=-1
print(ans)

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

for i in range(2**n):
  count = [0]*(m+1)
  for j in range(n):
      if (i >> j) & 1:
        for k in range(m+1):
          count[k] += lst[j][k]
  judge = True
  for j in range(1, m+1):
    if count[j] < x:
      judge = False
      break
  if judge:
    ans = min(ans, count[0])
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Solution (Python):
import itertools


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

L = [0, 1]
num = N
bit_list = list(itertools.product(L, repeat=num))

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

if __name__ == "__main__":

    min_cost = float('inf')
    for bit in bit_list:
        cost = 0
        understand = [0 for _ in range(M)]
        for i in range(N):
            if bit[i] == 1:
                cost += C[i]
                for j in range(M):
                    understand[j] += A[i][j]
        
        clear = True
        for u in understand:
            if u < X:
                clear = False
                break
        
        if clear and cost < min_cost:
            min_cost = cost
    
    if min_cost == float('inf'):
        print(-1)
    else:
        print(min_cost)

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N, M, X = map(int, input().split())
    C = [0] * N
    A = []
    for n in range(N):
        s = list(map(int, input().split()))
        C[n] = s[0]
        A.append(s[1:])
    
    res = INF
    for bit in range(2**N):
        tmp = 0
        P = [0] * M
        for n in range(N):
            if (bit >> n) & 1:
                tmp += C[n]
                for m in range(M):
                    P[m] += A[n][m]
        flg = True
        for m in range(M):
            if P[m] < X:
                flg = False
        if flg:
            res = min(res, tmp)

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


if __name__ == '__main__':
    main()

Solution (Python):
n,m,x = map(int, input().split())
C = []
A = []
ans = 10**9
for i in range(n):
  AC = list(map(int,input().split()))
  C.append(AC.pop(0))
  A.append(AC)

for i in range(2**n):
  cost = 0
  crit = [0]*m
  for j in range(n):
    if (i>>j)& 1:
      for k in range(m):
        crit[k] += A[j][k]
      cost += C[j]
  if min(crit) >= x:
    ans = min(ans, cost)
  
if ans == 10**9:
  ans = -1
print(ans)

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[0])
    A.append(tmp[1:])

TF = [0,1]
L = list(itertools.product(TF, repeat=N))

out = float('inf')
for K in L:
    Cost = 0
    ML = [0]*M
    for i in range(N):
        if K[i]==1:
            for j in range(M):
                ML[j]+=A[i][j]
            Cost+=C[i]
    flag = 1
    for j in range(M):
        if ML[j]<X:
            flag = 0
    if flag==1:
        if Cost < out:
            out = Cost

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