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


min_val = sum(C)
ans = False

for bit in range(1 << N):
    R = [0] * M
    c = 0

    for i in range(N):
        if bit & (1 << i):
            c += C[i]
            for m in range(M):
                R[m] += A[i][m]

    if all([r >= X for r in R]):
        ans = True
        min_val = min(min_val, c)


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

Solution (Python):
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
sys.setrecursionlimit(150000)

N, M, X = map(int, sys.stdin.readline().split())
a = []
for i in range(N):
    a.append(inpl())
b = [0] * M
res = float("INF")
def dfs(cost, start, tmp):
    global res
    if min(tmp) >= X:
        res = min(res, cost)
        return res
    for i in range(start, N):
        c = tmp.copy()
        d = [i + j for i, j in zip(c, a[i][1:])]
        dfs(cost + a[i][0], i + 1, d)
    return res

ans = dfs(0,0,b)
if ans != float("INF"):
    print(ans)
else:
    print(-1)

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

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,M,X=nm()
C=[0]*N
A=[[0]*M for i in range(N)]
for i in range(N):
    tmp=nl()
    C[i]=tmp[0]
    A[i][:]=tmp[1:]

r=[[0]*M for i in range(2**N)]
cm=[0]*(2**N)
for i in range(2**N):
    sum_m=0
    for j in range(N):
        if((i>>j) & 1):
            sum_m+=C[j]
            for k in range(M):
                r[i][k]+=A[j][k]
    cm[i]=sum_m

inds=list(range(2**N))
inds.sort(key=lambda x: cm[x])

ind=0
while(ind<2**N):
    flag=True
    for i in range(M):
        if(r[inds[ind]][i]<X):
            flag=False
    if(flag==True):
        print(cm[inds[ind]])
        sys.exit(0)
    ind+=1

print(-1)

Solution (Python):
import itertools

n,m,x=list(map(int,input().split()))
C,li=[],[] 
ans=[]
for i in range(n):
  c,*A=list(map(int,input().split()))
  C.append(c)
  li.append(A)
  
for i in itertools.product([0,1],repeat=n):
  money=sum([y*z for (y,z) in zip(C,i)])
  U=[0 for _ in range(m)]
  for k,j in enumerate(i):
    if j:
      U=[x+y for (x,y) in zip(U,li[k])]
  if sum([u >= x for u in U]) == m:
    ans.append(money)
    
if ans == []:
  print("-1")
else:
  print(min(ans))

Solution (Python):


def solve():

    mini = 10**9
    combs = getcombs(n)
    for com in combs:
        skill = [0] * m
        price = 0
        for i in range(n):
            if int(com[i]):
                price += c[i]
                addvec(skill, a[i])
                if min(skill) >= x:
                    mini = min(mini, price)
    if mini!=10**9:
        print(mini)
    else:
        print(-1)
    return


def getcombs(n):
    combs = []
    for i in range(2**n):
        combs.append(format(i, '
    return combs






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



n,m, x = [int(i) for i in input().split(" ")]
c = []
a = []
for _ in range(n):
    read = [int(i) for i in input().split(" ")]
    c.append(read[0])
    a.append(read[1:])
solve()

Solution (Python):
import itertools

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

for i in range(2,N+1):
    b_pairs+=itertools.combinations(b,i)

for i in range(N):
    flag=1
    skill=[0]*M
    for j in range(M):
        skill[j]+=data[i][j+1]
    for j in range(M):
        if skill[j]<X:
            flag=0
    if flag==1:
        ans=min(ans,data[i][0])

for i in range(len(b_pairs)):
    skill=[0]*M
    sum=0
    flag=1
    for k in range(len(b_pairs[i])):
        sum+=data[b_pairs[i][k]][0]
        for j in range(1,M+1):
            skill[j-1]+=data[b_pairs[i][k]][j]
    for h in range(M):
        if skill[h]<X:
            flag=0
    if flag==1:
        ans=min(ans,sum)

if ans==999999999:
    ans=-1
print(ans)

Solution (Python):
N,M,X=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(N):
  ca=[int(x) for x in input().rstrip().split()]
  l.append(ca)

A=[0 for i in range(M+2)]
flag=1
ans=10**10
cnt=0
for i in range(2**N):
  flag=1
  cost=0
  for j in range(N):
    if i>>j & 1:
      now=l[N-j-1]
      cost+=now[0]
      for s in range(M):
        A[s]+=now[s+1]
  for t in range(M):
    if X<=A[t]:
      continue
    else:
      flag=0
      break
  if flag==1:
    ans=min(ans,cost)
    cnt+=1

  A=[0 for v in range(M+2)]

if cnt==0:
  print(-1)
else:
  print(ans)

Solution (Python):
INF = 10 ** 10
N, M, X = map(int, input().split())
C = list()
A = list()
for n in range(N):
    ca = list(map(int, input().split()))
    C.append(ca[0])
    A.append(ca[1:])
ans = INF
for n in range(2 ** N):
    m = [0] * M
    c = 0
    for nn in range(N):
        if (n & (1 << nn)) > 0:
            c += C[nn]
            for mm in range(M):
                m[mm] += A[nn][mm]
    if all([x >= X for x in m]):
        ans = min(ans, c)
print(ans if ans < INF else -1)

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

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

CA = []

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

CA = np.array(CA)

C = CA[:, 0]
A = CA[:, 1:]

whole = np.array(list(product([0,1],repeat=N)), np.bool)

ans_tmp = []

for p in whole:
    score = A[p].sum(axis=0)
    ans_tmp.append(score[np.where(score>=X)].shape[0]==M)

pattern = whole[ans_tmp]

score = A[whole[1]].sum(axis=0)

ans = 10**15
for p in pattern:
    tmp = C[p].sum()
    if ans > tmp:
        ans = tmp

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

Solution (Python):
import numpy as np
n,m,x = map(int,input().split())
c = []
A = np.array([[0]*m for _ in range(n)])
for i in range(n):
  a = list(map(int,input().split()))
  c.append(a[0])
  A[i] = np.array(a[1:])
ans = 10**18
for i in range(2**n):
  cost = 0
  u = np.array([0]*m)
  for j in range(n):
    if i >> j & 1:
      cost += c[j]
      u += A[j]
  flag = 1
  for j in range(m):
    if u[j] < x:
      flag = 0
  if flag == 1:
    ans = min(cost,ans)
if ans == 10**18:
  print(-1)
else:
  print(ans)

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

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

INF = 10**7
ans = INF
for t in range(2**N):
    tmp = 0
    check = [X]*M
    for i in range(N):
        if (t >> i) & 1 == 1:
            tmp += CA[i][0]
            for j in range(M):
                check[j] -= CA[i][j+1]
    for ch in check:
        if ch > 0:
            break
    else:
        if tmp < ans:
            ans = tmp

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

Solution (Python):

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

min_total = -1
for i in range(2 ** N):
    sub = 0
    skills = [0] * M

    for j in range(N):
        if (i >> j & 0b1) == 1:
            sub += books[j][0]
            for k in range(M):
                skills[k] += books[j][k + 1]

    for k in range(M):
        if skills[k] < X:
            break
    else:
        min_total = sub if min_total == -1 else min(min_total, sub)

print(min_total)

Solution (Python):
n,m,x = map(int,input().split())
c = []
a = []
for i in range(n):
    a1 = [int(i) for i in input().split()]
    c1 = a1.pop(0)
    a.append(a1)
    c.append(c1)
ans = []
for bit in range(1<<n):
    d = [0]*m
    price = 0
    for i in range(n):
        mask = 1<<i
        if mask&bit:
            price += c[i]
            for j in range(m):
                d[j] +=  a[i][j]
    flag = True
    for j in d:
        if j<x:
            flag = False
    if flag:
        ans.append(price)
print(min(ans) if len(ans)>0 else -1)

Solution (Python):
N, M, X = [int(i) for i in input().split()]
Cn = []
Anm = []
for n in range(N):
  Xn = [int(i) for i in input().split()]
  Cn.append(Xn[0])
  Anm.append(Xn[1:])

min_cost = 1e100
for i in range(2**N):
  is_buy = [i >> m  & 1 for m in range(N)]
  ms = [0] * M 
  cost = 0
  for n in range(N):
    if is_buy[n] == 1:
      cost += Cn[n]
      for m in range(M):
        ms[m] += Anm[n][m]
  if min(ms) >= X:
    min_cost = min(cost, min_cost)
if min_cost == 1e100:
  print(-1)
else:
  print(min_cost)

Solution (Python):
import numpy as np

def dfs(a, c, a_lis, i, total_c):
    global min_c
    if len(a_lis.shape) > 1:
        total_sum = np.sum(a_lis, axis=0)
        for j in range(len(total_sum)):
            if total_sum[j] < x:
                break
            if j == len(total_sum)-1:
                min_c.append(total_c)
    if i >= n:
        return 0
    dfs(a, c, np.vstack((a_lis, a[i])), i+1, total_c + c[i])
    dfs(a, c, a_lis, i+1, total_c)


n,m,x = map(int,input().split())
li = []
c = []
for i in range(n):
    li.append(list(map(int,input().split())))
    c.append(li[i].pop(0))
a = np.array(li)
total_sum = np.sum(a, axis=0)
for i in total_sum:
    if i < x:
        print(-1)
        exit()
min_c = []
dfs(a, c, np.zeros(m), 0, 0)
print(min(min_c))

Solution (Python):
import sys
import os
import itertools

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

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

    sum=0
    min=100000000
    A_sum=[0]*M
    for i in range(N):
        for li in itertools.combinations(range(0,N),i+1):
            
            sum=0
            A_sum=[0]*M
            for j in li:
                sum+=C[j]
                for l in range(M):
                    A_sum[l]+=A[j][l]
            
            for l in range(M):
                if A_sum[l]<X:
                    break
                if l==M-1 and min>sum:
                    min=sum

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys






from itertools import combinations as comb




stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

n,m,x = map(int, stdin.readline().rstrip().split())
numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]



rikai = [0] * m
l = [i for i in range(1,n+1)]
ans = 10**9
for i in l:
    books = list(comb(l,i))

    for j in books:
        
        pay = 0
        rikaii = rikai[:]
        for u in j:
            cost = numbers[u-1][0]
            skill = numbers[u-1][1:]
            pay += cost
            rikaii = [x + y for (x, y) in zip(rikaii, skill)]
        ok = 0
        for y in range(m):
            if rikaii[y] >= x:
                ok += 1
        if ok == m:
            ans = min(ans,pay)

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

Solution (Python):
def main():
    n,m,x = map(int,input().split())
    costs = [0] * n
    level_up = [[] for _ in range(n)]


    for i in range(n):
        c,*exp = map(int,input().split())
        
        costs[i] = c
        level_up[i] = list(exp)

    mn = 99999999999999999999999999999999999999999999999

    for i in range(2 ** n):
        cost = 0
        x_check = [0] * m
        for j in range(n):
            if i >> j & 1:
                cost += costs[j]
                for k,point in enumerate(level_up[j]):
                    x_check[k] += point
        
        if all(map(lambda o:o>=x,x_check)):
            mn = min(mn,cost)

    if mn == 99999999999999999999999999999999999999999999999:
        print(-1)
    else:
        print(mn)





if __name__ == '__main__':
    main()

Solution (Python):
import copy

n, m, x = map(int, input().split())
a = [0] * n
ans = 10 ** 7
c1 = [0] * m


def dfs(s, d, c):
    global ans
    c3=c.copy()
    if s == n:
        
        for u in range(m):
            if c[u] < x:
                return
        ans = min(d, ans)
        
        return
    dfs(s + 1, d, c3)
    for k in range(m):
        c3[k] += a[s][k + 1]
    dfs(s + 1, d + a[s][0], c3)


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

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

dfs(0, 0, c1)
print(ans)

Solution (Python):
import itertools
import numpy as np
n,m,x = map(int,input().split())
c = []
total = [0] * m
ans = float('inf')
finish = False
for i in range(n):
    c.append(list(map(int,input().split())))
for i in range(1,n+1):
    for comb in itertools.combinations(c,i):
        su = np.array(comb).sum(axis=0)
        if sum(su[1:] >= x) == m:
            ans = min(ans,su[0])
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Solution (Python):
from itertools import permutations


def resolve():
    n, m, x = map(int, input().split())
    inf = float('INF')
    data = [list(map(int, input().split())) for i in range(n)]

    if n > 6:
        d = get(data[:n//2], n//2, m)
        e = get(data[n//2:], n - n//2, m)
        d = merge(d,e,m)
    else:
        d = get(data, n, m)

    ans = inf
    for tt,cost in d.items():
        for t in tt:
            if x > t:
                break
        else:
            if ans > cost:
                ans = cost

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

def get(data, n, m):
    d = {}
    for b in range(1 << n):
        tmp = [0 for i in range(m)]
        cost = 0
        for i in range(n):
            if ((1<<i) & b) == 0:
                continue
            cost += data[i][0]
            for j in range(1,m+1):
                tmp[j-1] += data[i][j]
        tt = tuple(tmp)
        if tt not in d:
            d[tt] = cost
        else:
            if cost < d[tt]:
                d[tt] = cost
    return d

def merge(d,e,m):
    f = {}
    for k,v in d.items():
        for s,t in e.items():
            tt = tuple(k[i]+s[i] for i in range(m))
            cost = v + t
            if tt not in f:
                f[tt] = cost
            else:
                if cost < f[tt]:
                    f[tt] = cost
    return f

if __name__ == '__main__':
    resolve()

Solution (Python):
import numpy as np

N,M,X=map(int, input().split())
C=[]
A=[]

for i in range(N):
    Ctmp,*Atmp=map(int, input().split())
    C.append(Ctmp)
    A.append(np.array(Atmp))

sum = 0

arr=[]
tmpC=[]
tmpA=[]

for bit in range(1<<N): 
    tmpmon=0
    tmpX=np.array([0]*M)
    for i in range(N):
        mask = 1 << i
        if bit&mask: 
            tmpmon+=C[i]
            tmpX+=A[i]
    tmpC.append(tmpmon)
    tmpA.append(tmpX)


ans = 9999999999
for i in range(len(tmpC)):
    if np.amin(tmpA[i]) >= X:
        if ans > tmpC[i]:
            ans=tmpC[i]

if ans == 9999999999:
    ans = -1

print(ans)

Solution (Python):
import itertools





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


sankousyo = []
rikaido = [0]*M

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


minBag = 10**9


n = len(sankousyo)
for i in range(2 ** n):
    bag = []
    rikaido = [0]*M
    for j in range(n):  
        if ((i >> j) & 1):  
            bag.append(sankousyo[j][0])  
            
            flg = True
            for m in range(M):
                rikaido[m] += sankousyo[j][m+1]
                if rikaido[m] < X:
                    flg = False
            if flg == True and minBag > sum(bag):
                minBag = sum(bag)
    

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

Solution (Python):
n,m,x = map(int,input().split())
ls = []
for i in range(n):
    ca = list(map(int,input().split()))
    ls.append(ca)
    
pattern = [bin(i)[2:].zfill(n) for i in range(2**n)]

ans = 10000000
for i in ls:
    tmp = []
    for j in pattern:
        p2 = 0
        al = [0]*m
        for k in range(len(j)):
            if j[k] == "1":
                al = [x + y for (x, y) in zip(ls[k][1:], al)]
                p2 += ls[k][0]
        p = 0
        for k in al:
            if k < x:
                p += 1
                break
        if sum(al) < m*x:
          p += 1
        if p == 0:
            
            ans = min(ans,p2)
if ans == 10000000:
  print(-1)
else:
  print(ans)

Solution (Python):
N,M,X = map(int,input().split())
Book = []
for i in range(N):
  Book.append(list(map(int,input().split())))
Cost = 10**15
for i in range(2**N):
  cost = 0
  A = [0 for i in range(M)]
  num = []
  j = 0
  while i > 0:
    if i%2 == 1:
      num.append(j)
    i = i//2
    j += 1
  for k in num:
    A = [x+y for (x,y) in zip(A,Book[k][1:])]
    cost += Book[k][0]
  if min(A) >= X:
    if cost < Cost:
      Cost = cost
if Cost == 10**15:
  print(-1)
else:
  print(Cost)

Solution (Python):
N,M,X = map(int,input().split())
data = []
for _ in range(N):
    data.append(list(map(int,input().split())))
cost = float("inf")
for i in range(2**N):
    temp = [0] * (M+1)
    for j in range(N):
        if ((i>>j)&1):
            for x in range(M+1):
                temp[x] += data[j][x]
    count = 0
    for f in temp[1:]:
        if f < X:
            break
        count += 1
    if count == M:
        cost = min([cost,temp[0]])
if cost == float("inf"):
    print(-1)
else:
    print(cost)

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

books = [[int(i) for i in input().split()] for j in range(n)]

def check(lst):
    return all([i >= x for i in lst])

ans = float("inf")
for k in range(1<<n):
    lst = [sum([(books[i][sub+1] if (k & 1<<i != 0) else 0) for i in range(n)]) for sub in range(m)]
    if check(lst):
        ans = min(ans, sum([(books[i][0] if (k & 1<<i != 0) else 0) for i in range(n)]))

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

Solution (Python):



import itertools


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

    min_c = 10 ** 20
    for i in range(2 ** n):
        cur_c = 0
        a_list = [0] * m
        for j in range(n):
            is_use = i & (2 ** j)
            if is_use:
                cur_c += ca_list[j][0]
                a_list = [a_list[k] + ca_list[j][k + 1] for k in range(m)]
        if all(k >= x for k in a_list) and cur_c < min_c:
            min_c = cur_c
    print(min_c if min_c != 10 ** 20 else -1)


if __name__ == '__main__':
    main()

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

import numpy as np
skill = np.array([0 for i in range(m + 1)])
ans_buf = []

for i in range(1, 2 ** n):
    flag = True
    two = str(bin(i))
    two = two[2:].zfill(n)

    for j in range(n):
        if two[j] == '1':
            skill += np.array(buf[j])
    
    for j in range(m):
        if skill[j + 1] < x:
            flag = False
    if flag:
        ans_buf.append(skill)
    skill = np.array([0 for i in range(m + 1)])


ans = [i[0] for i in ans_buf]
if ans == []:
    ans = [-1]
ans = min(ans)
print(ans)

Solution (Python):



import sys
import itertools

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M, X = i2nn()
    C = [None] * N
    A = [None] * N
    sum_C_min = 0
    sum_A = [0] * M
    for i in range(N):
        C[i], *A[i] = i2nn()
        sum_C_min += C[i]
        for j in range(M):
            sum_A[j] += A[i][j]
    for a in sum_A:
        if a < X:
            print(-1)
            return
    for n in range(N - 1, 0, -1):
        sum_C_prev = sum_C_min
        for v in itertools.combinations(range(N), n):
            sum_C, ok = func(N, M, X, C, A, v)
            if ok and sum_C < sum_C_min:
                sum_C_min = sum_C
        if sum_C_prev == sum_C_min:
            print(sum_C_min)
            return
    print(sum_C_min)
    return

def func(N, M, X, C, A, v):
    sum_A = [0] * M
    sum_C = 0
    for i in v:
        sum_C += C[i]
        for j in range(M):
            sum_A[j] += A[i][j]
    for a in sum_A:
        if a < X:
            return sum_C, False
    return sum_C, True
main()

Solution (Python):


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

from itertools import combinations as c
add = lambda x,y: [i+j for i,j in zip(x,y)]
n,m,x = mp()
cost,mat = {},{}
for i in range(1,n+1):
    xx = ip()
    cost[i] = xx[0]
    mat[i] = xx[1:]
ans = []
rows = [i for i in range(1,n+1)]
for i in range(1,n+1):
    for j in list(c(rows,i)):
        t = [0]*m
        for k in j:
            t = add(t,mat[k])
        if all(ii>=x for ii in t):
            ans.append(sum([cost[ii] for ii in j]))
if ans == []:
    print(-1)
else:
    print(min(ans))

Solution (Python):


import itertools

n, m, x = map(int, input().split())
_list = [list(map(int, input().split())) for _ in range(n)]
n_list = [i for i in range(n)]
all_list = []
a = [0]*(m+1)
ans = 100000000000000000000000

for i in range(n):
    for j in itertools.combinations(n_list, i+1):
        all_list.append(j)

for i in all_list:
    a = [0]*(m+1)
    for j in i:
        for k in range(m+1):
            a[k] += _list[j][k]
    if a[0] < ans:
        if all(x <= a[i] for i in range(1, m+1)):
            ans = a[0]

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

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

c = []
for i in range(n):
  c.append(list(map(int, input().split())))
  
max = 999999999999
ans = max  
  
for i in range(2 ** n):
  list=[0]*(m+1)
  
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m+1):
        list[k] += c[j][k]

  if min(list[1:]) >= x:

    ans = min(ans, list[0])

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

Solution (Python):
import itertools as iter
import math as m

def main():
    N, M, X = list(map(int, input().split()))
    C = []
    for _ in range(N):
        C.append(list(map(int, input().split())))
    result = []
    for i in range(1, N+1):
        for c in iter.combinations(C, i):
            cost = 0
            s = [0] * (M+1)
            for x in c:
                for j, y in enumerate(x):
                    s[j] += y
                cost += x[0]
            if check(s[1:], X):
                result.append(cost)
    if len(result) > 0:
        print(min(result))
    else:
        print(-1)
    pass

def check(s, X) -> bool:
    return all([a >= X for a in s])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from collections import Counter
import itertools
import fractions




def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())

def LI(): return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'


p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")



N,M,X=MI()
CA=LLI(N)

mi=10000000000000
ans=0

for i in range(1,N+1):
    kumi = itertools.combinations(CA,i)
    for k in kumi:
        target=[0]*(M+1)
        su=0
       
        for x in k:
            target = [a + b for (a,b) in zip(x,target)]
            su+=x[0]
        flag=True   
        for j in range(1,len(target)):
            if X > target[j]:
                flag=False
                break
        if flag:    
            mi=min(mi,su)
            ans+=1
if ans ==0:
    print(-1)
else:
    print(mi)

Solution (Python):
from itertools import combinations as IC
N, M, X = map(int, input().split())
ans = 10 ** 100
L = [list(map(int, input().split())) for i in range(N)]

for i in range(1, N + 1):
  T = list(IC(list(range(N)), i))
  
  for j in T:
    t = 0
    l = [0] * M
    for n in list(j):
      for k in range(M+1):
        if k == 0:
          
          t += L[n][0]
        else:
          l[k-1] += L[n][k]
    if len([n for n in l if n >= X]) == M:
      
      ans = min(ans, t)
print(-1 if ans == 10 ** 100 else ans)

Solution (Python):
import numpy as np
from itertools import combinations
from functools import reduce
from operator import add

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

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

success = []


def get_sum_books(args):
    return reduce(add, args)


for i in range(1, N + 1):
    for c in combinations(books, i):
        res = get_sum_books(c)
        if min(res[1:]) >= X:
            success.append(res[0])

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

Solution (Python):
from itertools import product as pd
from collections import defaultdict as dd
n, m, x = map(int, input().split())
price_dic = {}

naiyo_dic = dd(lambda: dd(lambda: 0))
for i in range(1, n+1):
    A = list(map(int, input().split()))
    price_dic[i] = A[0]
    for j in range(1, m+1):
        naiyo_dic[i][j] = A[j]



def price_and_can(pattern):
    skill = [0] * (m+1)
    skill[0] = 10**5 + 1
    price = 0
    can_do = False
    for i, is_read in enumerate(pattern):
        book_num = i + 1
        if is_read == 1:
            price += price_dic[book_num]
            for j in range(1, m+1):
                skill[j] += naiyo_dic[book_num][j]
    if min(skill) >= x:
        can_do = True
    
    return price, can_do

prices = []
for pattern in pd([0, 1], repeat=n):
    val, can_do = price_and_can(list(pattern))
    if can_do:
        prices.append(val)


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

Solution (Python):
n, m, x = map(int, input().split())
t = []
ans = 0
for i in range(n):
    l = list(map(int, input().split()))
    t.append(l)
    ans += l[0]
maximum = ans + 10
ans = maximum
for i in range(1, 2**n):
    f = [c for c in format(i, f'0{n}b')]
    money = 0
    scores = [0]*m
    for l in [j for k, j in zip(f, t) if k == '1']:
        money += l[0]
        for j in range(1, m+1):
            scores[j-1] += l[j]
    if len(list(filter(lambda y: y >= x, scores))) == m:
        ans = min(ans, money)
print(ans if ans != maximum else -1)

Solution (Python):
N, M, X = 3, 3, 10
ARR = [
    [60, 2, 2, 4],
    [70, 8, 7, 9],
    [50, 2, 3, 9],
]

N, M, X = 3, 3, 10
ARR = [
    [100, 3, 1, 4],
    [100, 1, 5, 9],
    [100, 2, 6, 5]
]

N, M, X = 8, 5, 22
ARR = [
    [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],
]

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

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


def calculate(n, m, x, arr):
    result = []
    for i in range(2 ** n):

        tmpValue = 0
        mrr = [0] * m
        krr = [False] * m
        for j in range(n):
            res = i >> j & 1
            if res == 1:
                tmpValue = tmpValue + arr[j][0]
                for mIndex in range(m):
                    mrr[mIndex] = mrr[mIndex] + arr[j][mIndex + 1]
                    if mrr[mIndex] >= x:
                        krr[mIndex] = True
        if sum(krr) == m:
            result.append(tmpValue)

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


calculate(N, M, X, ARR)

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(10**6)

INF = 10**10


def main(input, print):
    n, m, x = map(int, input().split())
    table = [[] for _ in range(n)]
    for i in range(n):
        table[i] = list(map(int, input().split()))
    ans = INF
    for i in range(1, n+1):
        p = itertools.combinations(range(n), i)
        for pj in p:
            t = 0
            mt = [0] * m
            for k in range(len(pj)):
                t += table[pj[k]][0]
                for l in range(m):
                    mt[l] += table[pj[k]][l+1]
            is_ok = True
            for l in range(m):
                if mt[l] < x:
                    is_ok = False
            if is_ok:
                ans = min(ans, t)
    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

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


def taka(y,z):
    global hako
    if len(z) == n:
        hako.append(z)
        return
    zz = z.copy()
    zz.append(y)
    for i in range(2):
        taka(i,zz)


for i in range(2):
    taka(i,[])



sankousyo = []

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

takahasikunn = [0]*(m+1)

ans = 13*10**5

for i in hako:
    clear = 0
    for j in range(n):
        if i[j] == 1:
            for k in range(m+1):
                takahasikunn[k] += sankousyo[j][k]
    for l in range(1,m+1):
        if takahasikunn[l] >= x:
            clear += 1
    if clear == m:
        ans = min(ans,takahasikunn[0])
    
    takahasikunn = [0]*(m+1)

if ans == 13*10**5:
    ans = -1

print(ans)