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


import itertools

def add_lists(a, b):
    result = [0 for i in range(len(a))]
    for i in range(len(a)):
        result[i] = a[i] + b[i]
    return result

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

INF = float('inf')
ans = INF

for flags in itertools.product([0,1], repeat=n):
    tot = [0 for i in range(m)]
    now = 0
    for i in range(len(flags)):
        if flags[i] == 1:
            tot = add_lists(tot, a[i])
            now += c[i]
    flag = True
    for i in tot:
        if i < x:
            flag = False
    if flag:
        ans = min(ans, now)

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

Solution (Python):
import numpy as np

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


min=-1
for nnn in range(2**n):
    index=[]
    a=nnn
    for i in range(n):
        index.append(a%2)
        a//=2

    money=0
    xs=np.zeros(m)
    for i in range(n):
        if index[i]==1:
            money+=lis[i][0]
            xs+=np.array(lis[i][1:])
    if np.amin(xs)>=x:
        if min==-1:
            min=money
        elif min>money:
            min=money

print(min)

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



class Solver(object):

    def solve(self):

        def checker(current, X):
            for idx, value in enumerate(current):
                if idx == 0:
                    continue
                elif value < X:
                    return False
            return True

        def add_list(a, b):
            for i in range(len(a)):
                a[i] += b[i]
            return a

        N, M, X = [int(i) for i in input().split()]
        book_list = [[int(i) for i in input().split()] for _ in range(N)]
        init = [0] * (M + 1)
        ans = []
        for i in range(1 << N):  
            cur = [0] * (M + 1)
            for j in range(N):  
                if (i >> j) & 1:
                    cur = add_list(cur, book_list[j])
            if checker(cur, X):
                ans.append(cur[0])

        if len(ans) > 0:
            return min(ans)
        else:
            return -1


def main():
    solver = Solver()
    print(solver.solve())


if __name__ == "__main__":
    main()

Solution (Python):
import copy

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

Clist = []

for i in range(N):
    Clist.append(list(map(int, input().split())))

anslist = []


def dfs(index, tmplist):
    if index >= N:
        anslist.append(copy.copy(tmplist))
        return

    s = list(tmplist)

    for i in range(M+1):
        s[i] += Clist[index][i]

    dfs(index+1, s)
    dfs(index+1, tmplist)


dfs(0, [0]*(M+1))

ans = -1

for al in anslist:
    flg = True
    for a in range(1, M+1):
        if al[a] < X:
            flg = False

    if flg:
        if ans == -1:
            ans = al[0]
        else:
            ans = min(ans, al[0])


print(ans)

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 = []
for i in range(2**len(l)):
    l2 = []
    for j in range(len(l)):
        if (i >> j) & 1 == 1:
            l2.append(l[j])
    
    s = [0] * (m + 1)
    for j in range(len(l2)):
        for k in range(m + 1):
            s[k] += l2[j][k]
    ans.append(s)
min = float("INF")
for i in range(2 ** len(l)):
    c = 0
    for j in range(1, m + 1):
        if ans[i][j] >= x:
            c += 1
    if c == m and min > ans[i][0]:
        min = ans[i][0]
print(-1 if min == float("INF") else min)

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

ans = 100000000
l = 0
for i in range(2**n):
    ab = [0]*m
    kari = 0
    for j in range(n):
        if (i >> j) & 1:
            ab = [x + y for (x, y) in zip(ab, a[j])]
            kari += c[j]
    if all([z >= x for z in ab]):
        ans = min(ans,kari)
        l += 1

if l == 0:
    ans = -1

print(ans)

Solution (Python):
def mips():
    return map(int,input().split())
def msps():
    return map(str,input().split())

import sys
import itertools
N,M,X = mips()
know = dict()
price = [[] for _ in range(N)]
L = []
C = []
for i in range(M):
    know[i] = 0
for i in range(N):
    L.append([i for i in mips()])
    C.append(L[i][0])
    L[i].remove(L[i][0])
Money = []
paid = 0 
K = []
No = 0
P = []
Q = [i for i in range(N)]
for i in range(N+1):
    P.append(list(itertools.combinations(Q,i)))
for k in range(N+1):
    for el in P[k]:
        for book in el:
            K = L[book] 
            paid += C[book]
            for i in range(M):
                know[i] += K[i]
        for i in range(M):
            if know[i] < X:
                No = 1
                break
        if No == 0:
            Money.append(paid)
        paid = 0
        No = 0
        for i in range(M):
            know[i] = 0
if Money == []:
    print("-1")
else:
    print(min(Money))

Solution (Python):
n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
ans=1e15
for f in range(1<<n):
  p,c=[0]*m,0
  for i in range(n):
    if f%2:
      p=list(map(lambda x,y:x+y,p,a[i][1:]))
      c+=a[i][0]
    f//=2
  if all(p[i]>=x for i in range(m)):
    ans=min(ans,c)
print(-1 if ans>=1e15 else ans)

Solution (Python):

inf = pow(10, 9) + 7

def solve(m, x, bag):

    p = [0]*(m+1)

    for i in range(len(bag)):
        for j in range(m+1):
            p[j] += bag[i][j]

    for i in range(1,m+1):
        if p[i] < x:
            return inf
    else:
        return p[0]

if __name__ == '__main__':

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

    mini = inf

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

        for j in range(n):
            if((i >> j) & 1):
                bag.append(l[j])
        
        r = solve(m, x, bag)
        if mini > r:
            mini = r

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

Solution (Python):
import sys
N,M,X=map(int, sys.stdin.readline().split())
C=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

ans=float("inf")

for n in range(2**N):
    L=[0 for _ in range(M+1)]
    price=0
    for i in range(N):
        if n>>i&1==1:
            for j,x in enumerate(C[i]):
                if j==0:
                    price+=x
                else:
                    L[j]+=x    
        if X<=min(L[1:]):
            ans=min(ans,price)
if ans==float("inf"):
    print -1
else:
    print ans

Solution (Python):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''










n,m,x = list(map(int, input().split()))
costlist = []
info = []
for i in range(n):
    temp = list(map(int, input().split()))
    costlist.append(temp[0])
    info.append(temp[1:])

ans = 10**9
for i in range(2**n):
    bits = ValueToBits(i,n)
    sums = [0 for j in range(m)]
    costs = 0
    for j in range(n):
        if (bits[j]==1):
            costs+= costlist[j]
            for l in range(m):
                sums[l] += info[j][l]
    ok = 1
    for l in range(m):
        if(sums[l] < x):
            ok = 0
    if(ok == 1):
        ans = min(ans, costs)


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

Solution (Python):
from itertools import combinations

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

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

s = float('inf')
r = False

for i in range(1, N + 1):
    C = combinations(range(0, N), i)
    for c in C:
        _s = 0
        t = [0 for _ in range(M)]
        for _c in c:
            _s += L[_c][0]
            for k in range(M):
                t[k] += L[_c][k + 1]
        _r = True
        for _t in t:
            if _t < X:
                _r = False
                break
        if _r and _s < s:
            r = True
            s = _s
if r:
    print(s)
else:
    print(-1)

Solution (Python):
from itertools import combinations

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



min_cost = 10**9
unst_flag = False

for i in range(1, n+1):
    combi_lists = list(combinations(range(n), i))

    for combi_list in combi_lists:
        tmp_list = list()
        for j in range(1,m+1):
            tmp_unst = 0
            for k in combi_list:
                tmp_unst += cost_lists[k][j]

            tmp_list.append(tmp_unst)
        
        if min(tmp_list) >= x:
            tmp_cost = 0
            for k in combi_list:
                tmp_cost += cost_lists[k][0]

            min_cost = min(min_cost, tmp_cost)
            unst_flag = True

if unst_flag:
    print(min_cost)
else:
    print(-1)

Solution (Python):

from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n, m, x = map(int, input().split())
    c = []
    a = []
    cost_list = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        c.append(tmp[0])
        a.append(tmp[1: m + 1])
    for i in range(1, n + 1):
        sets = list(itertools.combinations(range(1, n+1), i))
        
        for j in sets:
            cost = 0
            a_score = [0]*m
            for k in j:
                cost += c[k - 1]
                for l in range(m):
                    a_score[l] += a[k - 1][l]
            flg = 0
            for k in a_score:
                if k < x:
                    flg = 1
            if flg == 0:
                cost_list.append(cost)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

class A:

    def solve(self):
        s1 = input()
        s2 = input()
        print("Yes" if s1 == s2[:-1] else "No")

class B:

    def solve(self):
        A, B, C, K = tuple(map(int, input().split(" ")))
        sum = min(A, K)
        K -= A
        K -= B
        sum -= max(min(K, C), 0)
        print(sum)

class C:

    def solve(self):
        n, m, t = tuple(map(int, input().split(" ")))
        costs = []
        matrix = [[0 for x in range(m)] for y in range(n)]

        for i in range(n):
            line = [int(x) for x in input().split(" ")]
            costs.append(line[0])
            for j in range(len(line[1:])):
                matrix[i][j] = line[j+1]

        end = 2**n
        min_cost = sys.maxsize
        for i in range(end):
            binary = [int(x) for x in ("{:032b}".format(i))[-n:]]
            skills = list(map(lambda x: x[1], filter(lambda x: x[0] == 1, zip(binary, matrix))))
            acc = [0 for x in range(m)]

            for x in skills:
                acc = [x + y for x,y in zip(acc, x)]

            if all(map(lambda x: x >= t, acc)):
                ccost = sum(map(lambda x: x[1], filter(lambda x: x[0] == 1, zip(binary, costs))))
                if min_cost > ccost:
                    min_cost = ccost

        print(min_cost if min_cost != sys.maxsize else -1)

C().solve()

Solution (Python):
from itertools import combinations

def Main(N, M, X, C, A):
    inds = list(range(N))
    ind_subset = []
    for i in range(1, N+1):
        for c in combinations(inds, i):
            ind_subset.append(c)
    ans = []
    for e in ind_subset:
        c = 0
        a = [0]*M
        for j in e:
            c += C[j]
            a = [a[k]+A[j][k] for k in range(M)]
        if min(a) >= X:
            ans.append(c)
    if len(ans) == 0:
        return -1
    else:
        return min(ans)      
    
def main():
    N, M, X = map(int, input().split())
    B = []
    C = []
    A = []
    for i in range(N):
        B = list(map(int, input().split()))
        c = B[0]
        a = B[1:]
        C.append(c)
        A.append(a)
    print(Main(N, M, X, C, A))

if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import numpy as np

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

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

all_list = []
for i in range(1, len(C_A_list)+1):
    for j in itertools.combinations(C_A_list, i):
        all_list.append(list(j))

cost_list = []
for comb in all_list:
    comb_ = np.array(comb)
    if [i >= X for i in sum(comb_)[1:]] == [True] * M :
        cost_list.append(sum(comb_)[0])

if len(cost_list) > 0:
    print(min(cost_list))
else:
    print(-1)

Solution (Python):
def avi_chk(X,avi_list):
    for a in avi_list:
        if a<X:
            return False
    return True

def t1():
    import numpy as np

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

        avility.append(c)
        
    min_v=-1
    for i in range(2**N):
        v=0
        now_avi=np.zeros(M)
        for j in range(N):
            if((i>>j)&1):
                now_avi+=avility[j][1::]
                v+=avility[j][0]
        if avi_chk(X,now_avi):
            if min_v==-1:
                min_v=v
            elif min_v>v:
                min_v=v
    print(min_v)

            
        
                

      
if __name__ == '__main__':
    t1()

Solution (Python):
N,M,X = map(int, input().split())
book = []
hm = []
total_price = []
for i in range(N):
  one = list(map(int, input().split()))
  hm.append(one[0])
  one.pop(0)
  book.append(one)

for i in range(2 ** N):
  sougaku = 0
  point = [0] * M
  for j in range(N):
    if ((i >> j) & 1):
      point = [x + y for (x, y) in zip(point,book[j])]
      sougaku += hm[j]
  if min(point) >= X:
    total_price.append(sougaku)

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

Solution (Python):
from operator import add
n,m,x = map(int,input().split())
matrix = []
sum_list = [0 for i in range(m+1)]
for i in range(n):
    tmp = list(map(int,input().split()))
    matrix.append(tmp)
def tansaku(l,s):
    
    if len(l) == 0:
        if min(s[1:]) >= x:
            return s[0]
        else:
            return 10 ** 8
    else:
        tmp1 = tansaku(l[1:],s)
        s = list(map(add,s,l[0]))
        tmp2 = tansaku(l[1:],s)
        return min(tmp1,tmp2)
ans = tansaku(matrix,sum_list)
if ans == 10**8:
    print(-1)
else:
    print(ans)

Solution (Python):
import copy
import itertools
import sys

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

us = [0 for _ in range(m)]

l = []
for i in range(n):
    row = [int(i) for i in input().split()]
    l.append(copy.deepcopy(row))


first = []
c = 0
for i in range(1, n+1):
    c = itertools.combinations(range(n), i)
    for v in c:
        total = 0
        for e in v:
            total += l[e][1]
        if total >= x:
            first.append(v)

for i in range(2, m+1):
    cc = copy.deepcopy(first)
    first = []
    for v in cc:
        total = 0
        for e in v:
            total += l[e][i]
        if total >= x:
            first.append(v)

if len(first) == 0:
    print(-1)
    sys.exit()

ans = (100000*n)+1
for i in first:
    t = 0
    for j in i:
        t += l[j][0]
    if ans > t:
        ans = t

print(ans)

Solution (Python):
from itertools import compress, product

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

for p in product(range(2), repeat=N):
    sumlist = [0] * (M+1) 
    for c in compress(clist, p):
        for i, val in enumerate(c):
            sumlist[i] += val
    if all(i >= X for i in sumlist[1:]):
        prices.append(sumlist[0])

if prices:
    print(min(prices))
else:
    print(-1)

Solution (Python):
import itertools

books = {}
name = 1
N,M,X = map(int, input().split())
for i in range(N):
    book = [int(i) for i in input().split()]
    books[name] = book
    name += 1

choices = []
for i in range(len(books.keys())):
    for j in itertools.combinations(books.keys(), i+1):
        choices.append(j)

prizes = []
for choice in choices:
    
    prize = 0
    score = [0]*M
    for num in choice:
        prize += books[num][0]
        score = [score[i]+books[num][i+1] for i in range(0,len(score))]
    
    
    
    if X<=min(score): 
        prizes.append(prize)
    
if len(prizes) != 0: print(min(prizes))
else: print('-1')

Solution (Python):
import numpy as np
from functools import reduce
import math

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

books = []
moneys = []
for i in range(N):
    C = list(map(int, input().split()))
    moneys.append(C[0])
    books.append(np.array(C[1:]))
moneys = np.array(moneys)
books = np.array(books)

coms = [np.array(list(map(int, bin(i)[2:].rjust(N, "0")))) for i in range(2**N)]

min_val = math.inf
for com in coms[1:]:
    if sum([X]*M <= reduce(lambda a, b: a+b, books[com==1])) == M:
        min_val = min(min_val, sum(moneys[com==1]))
        
if min_val == math.inf:
    print(-1)
else:
    print(min_val)

Solution (Python):
import numpy as np
n, m, x = map(int,  input().split())
c=[]
a=[]
for _ in range(n):
    y = list(map(int, input().split()))
    c.append(y[0])
    a.append(y[1:])
    
def dfs(i, sum_c, sum_a):
    if i==n:
        if sum(sum_a>=x) == m:
            return sum_c
        else:
            return 10**12
    s1=dfs(i+1, sum_c+c[i], sum_a+np.array(a[i]))
    s2=dfs(i+1, sum_c, sum_a)
    return min(s1, s2)
  
ans=dfs(0, 0, np.array([0]*m))
if ans==10**12:
    print(-1)
else:
    print(ans)

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

I = []

for i in range(n):
  I.append(list(map(int, input().split())))
    
ans = 10000000000000
  
for i in range(1<<n):
  u = [0] * m
  c = 0
  for j in range(n):
    if (i>>j) % 2 == 1:
      for k in range(m):
        u[k] += I[j][k+1]
      c += I[j][0]
        
  flag = 1
  for e in u:
    if e < x:
      flag = 0
      
  if min(u) < x:
    continue
  else:
    ans = min(ans, c)

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

Solution (Python):
import numpy as np
import itertools
N,M,X=map(int,input().split())
a=[]
b=[]
seq=[]

for i in range(0,N):
    seq.append(i)
for _ in range(0,N):
    a.append(list(map(int,input().split())))
a=np.array(a)
ans=10**7+1
for j in range(1,N+1):
    alist=list(itertools.combinations(seq,j))
    for k in range(len(alist)):
        b=list(alist[k])
        c=sum(a[b])
        if min(c[1:])>=X:
            ans=min(ans,c[0])
if ans==10**7+1:
    print(-1)
else:
    print(ans)

Solution (Python):
import itertools

def main(N, M, X, CA):
    cand = []
    for n in range(N):  
        for ca in itertools.combinations(CA, n+1):
            s, price = f(ca)
            if all(i >= X for i in s):
                cand.append(price)
    if len(cand) == 0:
        print(-1)
    else:
        print(min(cand))


def f(lst):
    s = [0 for _ in range(M)]
    price = 0
    for ca in lst:
        price += ca[0]
        for i in range(M):
            s[i] += ca[i+1]
    return s, price





if __name__ == '__main__':
    N, M, X = list(map(int, input().split()))
    CA = []
    for _ in range(N):
        CA.append(list(map(int, input().split())))

    main(N, M, X, CA)

Solution (Python):

n, m, x = map(int, input().split())
cs = [0] * n
As = [[0] * m] * n

for i in range(n):
    cs[i], *As[i] = list(map(int, input().split()))

ans = 10 ** 8  

for i in range(2 ** n):
    
    amount = 0
    probs = [0] * m
    flags = bin(i)[2:].zfill(n)

    for j in range(n):
        c = cs[j]
        val = int(flags[j])
        amount += val * c
        for k in range(m):
            probs[k] += val * As[j][k]

    if (len(list(filter(lambda p: p < x, probs))) == 0):
        ans = min(ans, amount)


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

Solution (Python):
N,M,X=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
ANS=[]
now=[0]*(M+1)
i=0
j=0
def choice(now,A,i,N,ANS):
    if i==N-1:
        add=[x+y for (x,y) in zip(now,A[i])]
        ANS.append(now)
        ANS.append(add)
    else:
        add=[x+y for (x,y) in zip(now,A[i])]
        choice(now,A,i+1,N,ANS)
        choice(add,A,i+1,N,ANS)

choice(now,A,i,N,ANS)
ans=1200001
for i in range(len(ANS)):
    for j in range(1,M+1):
        if ANS[i][j]<X:
            break
    else:
        ans=min(ans,ANS[i][0])
if ans==1200001:
    ans=-1
print(ans)

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

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

goal = [x] * (m)

def infer(ans):
    for i in range(m):
        if goal[i] > ans[i]:
            return False
    return True

cost = 10 ** 12
flag = False
for i in range(2**n):
    bag = [0] * (m)
    total = 0
    for j in range(n):  
        if ((i >> j) & 1):
            bag = [bag[k] + a[j][k] for k in range(m)]
            total += c[j]
    
    if infer(bag):
        cost = min(cost, total)
        flag = True
print(cost if flag else -1)

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

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

result = []
for n in range(2 ** N):
    ii = [0] * N
    for i in range(N):
        if (n >> i) & 1:
            ii[i] = 1
    
    tmp = [0] * (M + 1)
    for j in range(len(ii)):
        if ii[j] == 1:
            tmp = (np.array(tmp) + np.array(C[j])).tolist()
    result.append(tmp)


def ex(array):
    for i in array[1:]:
        if i < X:
            return False
    return True


min_value = sys.maxsize
result.sort()
for r in result:
    if ex(r):
        print(r[0])
        exit()

print(-1)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from itertools import product

N,M,X = LI()
C = [0]*N
A = []
for i in range(N):
    x = LI()
    C[i] = x[0]
    A.append(x[1:])

Z = list(product([False,True],repeat=N))
ans = float('inf')
for z in Z:
    cost = 0
    rikai = [0]*M
    for i in range(len(z)):
        if z[i]:
            cost += C[i]
            for j in range(M):
                rikai[j] += A[i][j]
    flag = False
    for i in range(M):
        if rikai[i] < X:
            flag = True
            break
    if not flag:
        if cost < ans:
            ans = cost

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

Solution (Python):
n,m,x=map(int,input().split())
c=[]
a=[]

for i in range(n):
    ca=list(map(int,input().split()))
    c.append(ca[0])
    a.append(ca[1:])
ok=False
money=[]

for cnt in range(2**n):
    aa=[0 for j in range(m)]
    mon=0
    for i in range(n):
        if 2**i & cnt !=0:
            mon+=c[i]
            for mm in range(m):
                aa[mm]+=a[i][mm]
    if min(aa) >= x:
        ok = True
        money.append(mon)

if ok:
    print(min(money))
else:
    print(-1)

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


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

Cs = []

for _ in range(N):
    Cs.append(list(map(int,(input().split()))))

Cs = np.array(Cs)

patterns = product([0, 1], repeat=N)

ans = 10**12

for pattern in patterns:
    
    for i in range(len(pattern)):
        en = 0
        unds = np.array([0]*M)
        for p in range(len(pattern)):
            if pattern[p] == 1:
                unds += Cs[p, 1:]
                en += Cs[p][0]
                if all([u >= X for u in unds]):
                    
                    ans = min(ans, en)

if ans == 10**12:
    print(-1)
    sys.exit()


print(ans)

Solution (Python):
import itertools

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

List = []

Max = 10 ** 7

for i in range(N):
    List.append(list(map(int, input().split())))


l = []
for i in range(N):
    l.append(i)

for i in range(N, 0, -1):
    for j in itertools.combinations(l, i):
        Sum = [0] * (M+1)
        flg = 0
        for k in j:
            for h in range(M+1):
                Sum[h] += List[k][h]
        
        if Sum[0] <= Max:
            for a in range(1, M+1):
                if Sum[a] < X:
                    flg = 1
                    break
            if flg == 0:
                Max = Sum[0]

if Max == 10 ** 7:
    print(-1)
else:
    print(Max)

Solution (Python):
import itertools
n, m, x = map(int, input().split())
lst = []

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

ans_list = []

for i in range(1, n + 1):
    for j in itertools.combinations(lst, i):
        under_list = [0] * m
        money = 0
        for k in j:
            money += k[0]
            for i in range(m):
                under_list[i] += k[i + 1]
        if all([i >= x for i in under_list]):
            ans_list.append(money)

if not ans_list:
    ans = -1
else:
    ans = min(ans_list)

print(ans)

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

mi = 1 << 100
for i in range(1 << N):
    B = [0] * M
    c = 0
    for j in range(N):
        if i >> j & 1:
            a = A[j]
            c += C[j]
            for k in range(M):
                B[k] += a[k]
    if min(B) >= X:
        mi = min(mi, c)

print(mi if mi < 1 << 99 else -1)

Solution (Python):
import itertools
n, m, x = map(int, input().split())
c = []
ans = []
for _ in range(n):
    l = list(map(int, input().split()))
    c.append(l)

for i in range(1, n+1):
    for vl in itertools.combinations(c, i):
        a = [0] * m
        p = 0
        for v in vl:
            p += v[0]
            for j in range(m):
                a[j] += v[1+j]
        flag = True
        for k in range(m):
            if a[k] < x:
                flag = False
        if flag:
            ans.append(p)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

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

n, m , x = list(map(int, input().split()))
c = np.empty((n, 1))
a = np.empty((n, m))

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

max_score = sum(a)

if 1 in (max_score < x):
  print(-1)
  exit()

min_price = 10 ** 10

for i in range(n):
  pairs = iters.combinations(range(n), i+1)
  for pair in pairs:
    price = 0
    check = np.zeros((1, m))
    for idx in pair:
      price += c[idx]
      check += a[idx]
    if 1 not in (check < x):
      if price < min_price:
        min_price = price

print(int(min_price))

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

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

A=[]
C=[]
for n in range(N):
	A.append(CA[n][1:])
	C.append(CA[n][0])

B=[0]*M

for n in range(N):
	for m in range(M):
		B[m] += A[n][m]






if min(B) < X:
	print(-1)
	exit(0)



from itertools import product
L = list( product([0,1], repeat=N) )



from operator import add

ans = sum(C)
for l in L:
	sumA = [0]*M
	sumC = 0
	for i,x in enumerate(l):
		if x==0: continue
		sumA = map(add, sumA, A[i])
		sumC += C[i]
		
	if min(sumA) < X: continue
	
	ans = min(ans, sumC)

print(ans)

Solution (Python):


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

op_cnt = n  

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

ans = float('inf')
Flg = False
for i in range(2 ** op_cnt):
    money = 0
    A = [0] * m
    op = [True] * op_cnt  
    for j in range(op_cnt):
        if ((i >> j) & 1):
            op[op_cnt - 1 - j] = False  
    for j in range(n):
        if op[j]:
            money += C[j]
            for k in range(m):
                A[k] += L[j][k]
    flg = True
    
    for a in A:
        if a < x:
            flg = False
    if flg:
        ans = min(ans,money)
        Flg = True

if Flg:
    print(ans)
else:
    print('-1')