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 itertools
n, m, x = map(int, input().split())
a = []
ans = 12 * 10**6
flg = False
for i in range(n):
    a.append([int(x) for x in input().split()])
for j in range(1, n+1):
    for z in itertools.combinations([y for y in range(1, n+1)], j):
        A = [0]*m
        M = [False]*m
        for k in range(m):
            C = 0
            for zz in z:
                C += a[zz-1][0]
                A[k] += a[zz-1][k+1]
                if A[k] >= x:
                    M[k] = True
            if False not in M:
                if ans > C:
                    ans = C
                    flg = True
if flg:
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import defaultdict

n,m,x=map(int, input().split())
c=[]
tab=[]
cost = 10000000000
for i in range(n):
    A=[int(i) for i in input().split()]
    tab.append(A[1:])
    c.append(A[0])
for i in range(1<<n):
    tmp=0
    res = [0]*m
    for j in range(n):
        if(i&(1<<j)):
            tmp+=c[j]
            for k in range(m):
                res[k]+=tab[j][k]
    f=True
    for v in res:
        if v<x:
            f=False

    if f:
        cost = min(cost, tmp)



if cost!=10000000000:
    print(cost)
else:
    print(-1)

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

ok = False
ans = float('inf')
for bit in range(1 << n):
    o = [0] * m
    tot = 0
    for i in range(n):
        if bit >> i & 1:
            tot += c[i]
            for j in range(m):
                o[j] += a[i][j]

    allOk = True
    for i in o:
        if i < x:
            allOk = False
            break
    if allOk:
        ok = True
        ans = min(ans, tot)

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

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


cost = [B[i][0] for i in range(N)]

flag = False
min_ = float('inf')
for i in range(1 << N):
    cost_temp = 0
    cnt = 0
    skills = [0] * M
    while i > 0:
        if (1 & i):
            cost_temp += cost[cnt]
            for m in range(M):
                skills[m] += B[cnt][m + 1]

        cnt += 1
        i >>= 1

    flag2 = False

    for m in skills:
        if m < X:
            flag2 = True
            break

    if not flag2:
        flag = True
        min_ = min(min_, cost_temp)

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

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,M,X = inputMap()

	ans = 0
	inp = []
	for i in range(N):
		tmp = inputList()
		inp.append(tmp)

	ans = inf
	ans2 = ""
	for i in range(2**N):
		i_str = bin(i)
		i_str = i_str[2:]
		i_str = i_str[::-1]

		aaa = len(bin(2**N))-3 - len(i_str)
		for i in range(aaa):
			i_str += "0"

		

		skills = [0 for i in range(M)]
		tmp = 0
		for j,val in enumerate(i_str):
			if val == "1":
				kk = inp[j]
				for ii,vol in enumerate(kk):
					if ii == 0:
						tmp += vol
					else:
						
							
						skills[ii-1] += vol

		flg = True
		
		for vv in skills:
			if vv < X:
				flg = False
				break
		if flg == True:
			if ans > tmp:
				ans = tmp

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










def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

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

ans = np.inf
flag = 0
for i in range(2**n):
    r = np.array([0]*(m+1))
    for j in range(n):
        if (i>>j)&1:
            for k in range(m+1): r[k] += a[j][k]
    if np.all(r[1:]>=x):
        if ans > r[0]: ans = r[0]
        flag = 1
    else: flag = 0

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

Solution (Python):


import sys
import math
import itertools

debug = False

def log(text):
    if debug:
        print(text)


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
        (n, m, x) = [int(e) for e in lines[0].split(' ')]
        for _ in range(n):
            lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        (n, m, x) = [int(e) for e in lines[0].split(' ')]

    ca_list = []
    for i in range(1, n+1):
        ca_list.append([int(e) for e in lines[i].split(' ')])
        
    return (n, m, x, ca_list)


def solve(n, m, x, ca_list):


    result = 100000 * n + 1
    for p in itertools.product([0,1], repeat=n):

        index_set = set([i for i, b in enumerate(p) if b == 1])
        ca_list_tmp = [e for i, e in enumerate(ca_list) if i in index_set]

        if debug:
            log("index_set=%s" % index_set)
            log("ca_list_tmp=%s" % ca_list_tmp)
        
        total_c = 0
        total_a = [0 for _ in range(m)]
        r = True 
        for ca in ca_list_tmp:
            total_c = total_c + ca[0]

            for i in range(1, m + 1):
                total_a[i-1] = total_a[i-1] + ca[i]

        for i in range(m):
            if total_a[i] < x:
                r = False
                break
            
        if r:
            if total_c < result:
                result = total_c

    if result == 100000 * n + 1:
        result = -1

    return  result


def main():
    
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Solution (Python):
import itertools
from operator import add

n, m, x = map(int, input().split())
C = [[]] * (n + 1)
ans = -1

for i in range(1, n + 1):
    C[i] = list(map(int, input().split()))
for i in range(1, n + 1):
    pares = list(itertools.combinations(range(1, n + 1), i))
    for pare in pares:
        A = [0] * (m + 1)
        for el in pare:
            A = list(map(add, A, C[el]))
        flag = True
        for a in A[1:]:
            if not a >= x:
                flag = False
                break
        if flag:
            if A[0] < ans or ans == -1:
                ans = A[0]
print(ans)

Solution (Python):
import itertools

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

ok = False
cur_price = (10 ** 5) * n + 1
for i in range(1, n + 1):
    answers = list(itertools.combinations(range(n), i))
    
    for ans_list in answers:
        sum_list = [0] * (m + 1)
        
        for ans in ans_list:
            
            sum_list = [a + b for a, b in zip(sum_list, all_list[int(ans)])]
        
        if min(sum_list[1:]) >= x:
            if sum_list[0] < cur_price:
                cur_price = sum_list[0]
                ok = True

if ok:
    print(cur_price)
else:
    print(-1)

Solution (Python):
import itertools

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


All = [0] * (M+1)
for book in books:
  All = [x + y for (x, y) in zip(All, book)]
Min = All[0]
if all([i >= X for i in All[1:]]):
  for bks in itertools.product([0,1], repeat=N):
    ans = [0] * (M+1)
    par = [i for i, x in enumerate(bks) if x == 1]
    for book in par:
      ans = [x + y for (x, y) in zip(ans, books[book])]
    if all([i >= X for i in ans[1:]]) and Min > ans[0]:
      Min = ans[0]
  print(Min)
else: print(-1)

Solution (Python):
import numpy as np

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

minimum=10**7

for i in range(2**n):

  tmp=[]
  tmp2=[0]*(m+1)
  cnt=0
  for j in range(n):
    if ((i >> j) & 1):
      tmp.append(ca[j])
      cnt+=1

  for k in range(cnt):
    for l in range(m+1):
      tmp2[l]+=tmp[k][l]

  if min(tmp2[1:])>=x:
    minimum=min(minimum,tmp2[0])
print(minimum if minimum < 10**7 else '-1')

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

Alist = []
Clist = []

for i in range(N):
    tmpAlist = list(map(int, input().split()))
    Clist.append(tmpAlist.pop(0))
    Alist.append(tmpAlist)

min_money = 10 ** 5 * 12 + 1


for bits in range(1, 2 ** N):
    
    rikaido_list = [0] * M
    tmp_money = 0

    
    for bit_shift in range(N):
        if (bits >> bit_shift) & 1 != 1:
            continue
        
        tmp_money += Clist[bit_shift]
        for i in range(M):
            rikaido_list[i] += Alist[bit_shift][i]
    
    
    ok_flag = True
    for i in range(M):
        if rikaido_list[i] < X:
            ok_flag = False
            break  
    if ok_flag and tmp_money < min_money:
        min_money = tmp_money

if min_money < 10 ** 5 * 12 + 1:
    print(min_money)
else:
    print(-1)

Solution (Python):
import numpy as np

N, M, X = map(int, input().split())
books = [list(map(int, input().split())) for n in range(N)]
npbooks = np.array(books)

def can_achieve(points, target):
    return all(points >= target)

def make_subsets(whole_list):
    subsets = []
    for i in range(1 << len(whole_list)):
        output = []
        for j in range(len(whole_list)):
            if ((i >> j) & 1) == 1:
                output.append(whole_list[j])
        subsets.append(output)
    return subsets[1:]

subsets = make_subsets([i for i in range(N)])
values = []
for subset in subsets:
    total = np.array([0 for _ in range(M+1)])
    for idx in subset:
        total += books[idx]
    if can_achieve(total[1:], X):
        values.append(total[0])
if values == []:
    print(-1)
else:
    print(min(values))

Solution (Python):
import sys
N, M, X = map(int, sys.stdin.readline().split())
CA = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
C = [CA[i][0] for i in range(N)]
A = [CA[i][1:] for i in range(N)]
ans = 10 ** 20
for i in range(2 ** N):
    TMP = [0] * M
    op = [0] * N
    c = 0
    for j in range(N):
        if (i >> j) & 1:
            op[j] = 1
    for k in range(len(op)):
        if op[k]:
            TMP = list(map(lambda x,y: x + y, TMP, A[k]))
            c += C[k]
    TMP_2 = [l for l in TMP if l >= X]
    if len(TMP_2)== M:
        ans = min(ans, c)
if ans == 10 ** 20:
    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)]
bb=[0]*m
c=[]
cc=0
for i in range(n):
    cc+=a[i][0]
for i in range(m):
    for j in range(n):
        bb[i]+=a[j][i+1]
if any(bb[k]< x for k in range(m)):
  print(-1)
"""
d=[[] for i in range(m)]
money=0
i=0
def func(i,):
    if i==m:
        sum
        return money
    if func(i+1,money):
        return true
"""
def dec2bin(target):
    amari=[]
    while target !=0:
        amari.append(target % 2)
        target = target //2
    if len(amari)!=n:
        while len(amari)!=n:
            amari.append(0)
    amari.reverse()
    return amari
p=[]
for j in range(2**n):
    p.append(dec2bin(j))
for i in range(2**n):
    money=0
    b=[0]*m
    for j in range(n):
        if p[i][j]==1:
            money+=a[j][0]
            for aaa in range(m):
                b[aaa]+=a[j][aaa+1]
    if all(b[l]>=x for l in range(m)):
        c.append(money)

        
if len(c)>0:
  print(min(c))

Solution (Python):

import itertools
import numpy as np

def main():
    N, M, X = tuple(int(c) for c in input().split(' '))
    C = []
    A = []
    for _ in range(N):
        tmp = tuple(int(c) for c in input().split(' '))
        C.append(tmp[0])
        A.append(np.array(tmp[1:]))

    
    
    
    
    
    
    

    
    cmin = -1
    for n in range(1, N+1):
        for t in itertools.combinations(range(N), n):
            ri = np.zeros(M)
            ctmp = 0
            for i in t:
                ri += A[i]
                ctmp += C[i]
            if min(ri) >= X:  
                if cmin == -1:
                    cmin = ctmp
                elif ctmp < cmin:
                    cmin = ctmp
    print(cmin)

if __name__ == "__main__":
    main()

Solution (Python):



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




def listadd(a,b,n):
  c = [0] * n
  for i in range(n):
    c[i] = a[i]+b[i]
  return c

ans = 0
for candi in range(0,2**n): 
  s = [0] * (m + 1)

  for i in range(n):
    
    if candi >> i & 1:
      s = listadd(s,book[i],m+1)
  
  ck = 1
  for j in range(1,m+1):
    if s[j] < x:
      ck = 0
      break
    else:
      ck *= 1

  if ck:
    if ans:
      ans = min(ans,s[0])
    else:
      ans = s[0]

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

Solution (Python):
import numpy as np
import functools
import math
import collections
import scipy
import fractions
import itertools

def solve():
    n, m, x = map(int, input().split())
    c, a = [0]*n, [[] for i in range(n)]
    for i in range(n):
        hoge = list(map(int, input().split()))
        c[i], a[i] = hoge[0], hoge[1:m+1]
    hoge = list(range(n))
    cost = []
    kumi = []
    for i in range(2,n+1):
        kumi += list(itertools.combinations(hoge,i))
    for i in range(n):
        bit = 0
        for j in range(m):
            if a[i][j] < x:
                bit = 1
                break
        if bit == 0:
            cost.append(c[i])
    for i in range(len(kumi)):
        for j in range(m):
            huga = 0
            hoge = 0
            bit = 0
            for k in kumi[i]:
                huga += a[k][j]
                hoge += c[k]
            if huga < x:
                bit = 1
                break
        if bit == 0:
            cost.append(hoge)
    if len(cost) == 0:
        print(-1)
    else:
        print(min(cost))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import numpy as np
from itertools import chain,combinations
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def main():
    N, M, X = map(int, input().split())
    C = []
    A = []
    for _ in range(N):
        CA = list(map(int, input().split()))
        C.append(CA[0])
        A.append(CA[1:])
    score = [0] * M
    A = np.array(A)
    if np.sum(np.sum(A, axis=0) < X) > 0:
        print('-1')
    else:
        PS = list(powerset([i for i in range(N)]))
        min_money = 10**9
        for Set_list in PS:
            X_sum = np.zeros(M, dtype=int)
            money = 0
            for i in Set_list:
                X_sum += A[i]
                money += C[i]
            if np.sum(X_sum < X) == 0 and money < min_money:
                min_money = money
        print(min_money)
        

if __name__ == '__main__':
    main()

Solution (Python):
import itertools 
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in [0]*n]
cl, al = [], []
for c, *a in ca:
    cl += [c]
    al += [a]
za = [list(i) for i in zip(*al)]
if any(sum(i)<x for i in za):
    print(-1)
else:
    ans = sum(cl)
    for num in range(n-1, 0, -1):
        for i in itertools.combinations(ca, num):
            tmp = [0]*m
            c = 0
            for j in i:
                c += j[0]
                for k in range(m): tmp[k] += j[k+1]
            if all(i>=x for i in tmp):
                ans = min(ans, c)
    print(ans)

Solution (Python):
from itertools import combinations as comb
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(N)]
Cans = -1
for i in range(1, N+1):
    for lsts in comb(CA, i):
        Csum = 0
        buf = [0]*M
        for lst in lsts:
            Csum += lst[0]
            for j, v in enumerate(lst[1:]):
                buf[j] += v

        if Cans == -1 or Csum < Cans:
            flag = True
            for v in buf:
                if v < X:
                    flag = False
                    break
            if flag:
                Cans = Csum

print(Cans)

Solution (Python):

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

    ans = 1<<60
    for bit in range(1<<N):
        G = [0]*M
        cost = 0
        ok = False
        for i in range(N):
            if bit>>i & 1:
                c, *book = AB[i]
                cost += c
                for num, b in enumerate(book):
                    G[num] += b
        for g in G:
            if g < X:
                break
        else:
            ok = True
        if ok:
            ans = min(ans, cost)
    print(ans if ans < 1<<60 else -1)

if __name__ == "__main__":
    resolve()

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

N,M,X=(int(x) for x in input().rstrip('\n').split())
pat = [x for x in product([0,1], repeat=N)]
OK = []
C={}
for i in range(N):
  C[i]=[int(x) for x in input().rstrip('\n').split()]
for i in pat:
  ans = [0]*(M+1)
  for x in range(N):
    add =  [y*i[x] for y in C[x]]
    ans = [y + z for (y,z) in zip(add,ans)]
  if all(y>=X for y in ans[1:]):
    OK.append(ans[0])
if len(OK) >0:
  print(min(OK))
else:
  print('-1')

Solution (Python):
import numpy as np
import math


n,m,x = map(int, input().split())
lis = [np.asarray(list(map(int, input().split()))) for _ in range(n)]
lis = np.array(lis)

res = []
for i in range(2**n):
    t = np.array([0]*(m+1))
    for j in range(n):
        if ((i >> j) & 1):
            t += lis[j]
    res.append(t)

res = np.array(res)

z = math.inf

for i in res:
    if np.amin(i[1:]) >= x and i[0] < z:
        z = i[0]

print(z if z != math.inf else -1)

Solution (Python):
import math
import itertools

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

_min = float("inf")

for i in range(n):
    for j in list(itertools.combinations(range(n), i + 1)):
        _sum = [0 for _ in range(m)]
        cost = 0
        for jj in j:
            cost += li[jj][0]
        for l in range(1, m + 1):
            for k in j:
                _sum[l - 1] += li[k][l]
        flg = True
        
        for w in _sum:
            if x > w:
                flg = False
                break
        if flg:
            _min = min(_min, cost)
        
        
        

if math.isinf(_min):
    print(-1)
else:
    print(_min)

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

final_answer = float("inf")
for i in range(len(all_list)):
  anslist = [0]*(m+1)
  anscost = 0
  flag = True
  for j in range(n):
    if all_list[i][j] == 1:
      anscost += ca[j][0]
      for k in range(1,m+1):
        anslist[k] += ca[j][k]
  
  for l in range(1,m+1):
    if anslist[l] < x:
      flag = False
  if flag:
    ans_flag = True
    
    final_answer = min(final_answer,anscost)

if ans_flag:
  print(final_answer)
else:
  print("-1")

Solution (Python):
def mysum(A, B):
    C = [0] * len(A)
    for i in range(len(A)):
        C[i] = A[i] + B[i]
    return C


def mytruthy(A, X):
    for a in A:
        if a < X:
            return False
    return True


def c():
    N, M, X = map(int, input().split())
    R = {}
    costs = []

    for i in range(N):
        V = list(map(int, input().split()))
        if i == 0:
            R['0'*N] = [0] * (M + 1)
            R['1' + '0'*(N-1)] = V
            if mytruthy(V[1:], X):
                costs.append(V[0])
        else:
            newR = {}
            for k in R.keys():
                k2 = k[:i] + '1' + k[i+1:]
                newR[k2] = mysum(R[k], V)
                if mytruthy(newR[k2][1:], X):
                    costs.append(newR[k2][0])
            R.update(newR)

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



if __name__ == "__main__":
    c()

Solution (Python):

"""
@author: H_Hoshigi
"""

N, M, X = map(int, input().split())
cost_list = []
A_list_list = []
for i in range(N):
    input_list = list(map(int, input().split()))
    cost_list.append(input_list[0])
    A_list_list.append(input_list[1:])
max_cost = sum(cost_list)

def dfs(bool_list, min_cost):
    if len(bool_list) == N:
        cost = 0
        rikaido_list = [0 for k in range(M)]
        for i in range(N):
            if bool_list[i] :
                cost += cost_list[i]
                for j in range(M):
                    rikaido_list[j] += A_list_list[i][j]
        if min(rikaido_list)>=X:
            min_cost = min(min_cost, cost)
        return min_cost
    for b in [True, False]:
        bool_list.append(b)
        min_cost = min(min_cost, dfs(bool_list, min_cost))
        bool_list.pop()
    return min_cost

def main():
    min_cost = max_cost + 1
    min_cost = dfs([], min_cost)
    if min_cost > max_cost:
        min_cost = -1
    print(min_cost)

if __name__ == "__main__":
    main()

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

ans=float('inf')
for i in range(2**n):
  c=0
  s=[0]*m
  for b in range(n):
    if i>>b&1:
      c+=l[b][0]
      for j in range(m):
        s[j]+=l[b][j+1]
  if all([e>=x for e in s]):
    ans=min(ans,c)
if ans==float('inf'):
  ans=-1
print(ans)

Solution (Python):
N,M,X = map(int,input().split())
pA = [0]*N
for i in range(N):
    pA[i] = list(map(int,input().split()))
C = [0]*12
A = [0]*12
for i in range(N):
    C[i] = pA[i][0]
    A[i] = pA[i][1:]
minprice = sum(C)+1


for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        for i11 in range(2):
                                            for i12 in range(2):
                                                point = 0
                                                tasei = [0]*M
                                                price = 0
                                                itati = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12]
                                                for j in range(N):
                                                    price += itati[j]*C[j]
                                                    for k in range(M):
                                                        tasei[k] += itati[j]*A[j][k] 
                                               
            
                                                for i in range(M):
                                                    if tasei[i]>=X:
                                    
                                                        if i == M-1:
                                                            point = 1
                                                    else:
                                                        break
                                                    
                                                       
                                                
                                                if price < minprice and point == 1:
                                                    minprice = price
                                                  
if minprice == sum(C)+1:
    print(-1)
else:
    print(minprice)

Solution (Python):


import itertools


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



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


ans = -1
flg=1
for i in range(N+1):
    if i ==0:
        continue
    c = list(itertools.combinations(input_list, i))
    
    flg=1
    for l in c:
        
        flg=1
        for j in range(M):
            sum=0
            for k in range(i):
                
                sum=sum+l[k][j+1]
            
            if sum<X:
                flg=0
        if flg==1:
            sum=0
            for j in range(i):
                sum=sum+l[j][0]
            if ans==-1:
                ans = sum
            elif sum<ans:
                ans = sum
        


print(ans)

Solution (Python):
import itertools


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



INF = 10 ** 5 * 12 + 1
min_amount = INF
for i in range(1, N + 1):
    combinations = itertools.combinations(range(N), i)

    for combination in combinations:
        understanding_list = [0] * M
        amount = 0
        for i in combination:
            for j in range(1, len(CA[i])):
                understanding_list[j - 1] += CA[i][j]
            amount += CA[i][0]

        
        is_reached = all([understanding >= X for understanding in understanding_list])
        if not is_reached: continue

        min_amount = min(amount, min_amount)

answer = -1 if min_amount == INF else min_amount

print(answer)

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

import itertools
for i in range(1,n+1):
    c = list(itertools.combinations(CA,i))
    for j in c:
        com.append(j)
        
ans = 12*(10**5)+1
        
for i in com:
    res = [0]*(m+1)
    
    for j in range(len(i)):
        ca = i[j]
        
        for k in range(m+1):
            res[k] += ca[k]
            
    ok = 0        
    for j in res[1:]:
        if j >= x:
            ok += 1
            
        if ok == m:
            ans = min(ans,res[0])

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

Solution (Python):
from itertools import combinations as c

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

g = list(range(1, n + 1))

h = -1
for i in range(1, n + 1):
	for p in c(g, i):
		s = 0
		r = [0] * m
		for v in p:
			s += arr[v-1][0]
			for k in range(m):
				r[k] += arr[v-1][k+1]
		u = 1
		for v in r:
			if v < x:
				u = 0
		if u:
			if h == -1:
				h = s
			else:
				h = min(h, s)
print(h)

Solution (Python):
n,m,x = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(n)]
import itertools
max_=-1
for i in range(n):
    c_list = list(itertools.combinations(c, i+1))
    for j in c_list:
        d=[0]*(m+1)
        for k in j:
            d = [x+y for (x,y) in zip(d,k)]
        f=1

        for l in range(1,m+1):

            if d[l] < x:
                f=0
                break

        if f==1:
            if max_ ==-1:
                max_ = d[0]
            elif d[0] < max_:
                max_ = d[0]

print(max_)

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

ans = 1000000000
for i in range(1,n+1):
    for v in itertools.combinations(ab, i):
        memo = [0]*(m+1)
        for k in v:
            for l in range(m+1):
                memo[l] += k[l]
            flag = True
            for o in range(1,m+1):
                if memo[o] < x:
                    flag = False
        if flag:
            ans=min(memo[0],ans)

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