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


ans = 1300000
idx = [i for i in range(N)]
for i in range(1, N+1):
    combs = list(itertools.combinations(idx, i))
    for comb in combs:
        c = 0
        a = [0]*M
        for j in comb:
            c += C[j]
            for k in range(M):
                a[k] += A[j][k]
        if len([x for x in a if x<X]) == 0 and c < ans:
            ans = c


print(-1 if ans == 1300000 else ans)

Solution (Python):
import itertools


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

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

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

min_cost = float('inf')
for i in range(1,n+1):
    for seq in itertools.combinations(range(n),i):
        tmp_a = [0]* m
        flag = True
        sum_cost = 0
        for j in seq:
            sum_cost += c[j]
            for k in range(m):
                tmp_a[k]+= a[j][k]
                
        for k in range(m):
            if tmp_a[k] < x:
                flag = False
                break
        if flag:
            if min_cost > sum_cost:
                min_cost = sum_cost

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

Solution (Python):
from itertools import product

N, M, X = [int(x) for x in input().strip().split(" ")]
C = []
A = []

for _ in range(N):
    v = [int(x) for x in input().strip().split(" ")]
    c = v.pop(0)
    C.append(c)
    A.append(v)

sums = []
patterns = product(*[(0, 1) for _ in range(N)])
for pattern in patterns:
    price = 0
    status = [0 for _ in range(M)]
    for i, p in enumerate(pattern):
        price += C[i] * p
        for j in range(M):
            status[j] += A[i][j] * p
    if min(status) >= X:
        sums.append(price)

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

Solution (Python):
import sys
import itertools

n, m, x = map(int, input().split())
a = []
c = []
for _ in range(n):
    lst = list(map(int, input().split()))
    c.append(lst[0])
    a.append(lst[1:])
ans = 1000 * 1000 * 1000 * 100
for i in itertools.product('01', repeat=n):
    cur = 0
    algs = [0] * m
    for j in range(len(i)):
        if i[j] == '1':
            cur += c[j]
            for k in range(len(a[j])):
                algs[k] += a[j][k]
    for p in algs:
        if p < x:
            break
    else:
        ans = min(ans, cur)

if ans == 1000 * 1000 * 1000 * 100:
    print(-1)
else:
    print(ans)

Solution (Python):
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))

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

arr = []
for _ in range(n):
    i = map(int, input().split())
    arr.append((next(i), [*i]))

min_cost = float('inf')
for s in powerset(range(n)):
    cost = 0
    cur = [0]*m
    for i in s:
        cost += arr[i][0]
        for j in range(m):
            cur[j] += arr[i][1][j]

    ans = True
    for i in cur:
        if i < x:
            ans = False

    if ans:
        min_cost = min(min_cost, cost)


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

Solution (Python):

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

comb = []
l = [i for i in range(n)]
for i in range(n+1):
    comb.append(list(itertools.combinations(l, i)))


rikai = [0 for i in range(m)]
ans = pow(10, 1000)
tmp = 0
for i in range(len(comb)):
    for j in range(len(comb[i])):
        for h in comb[i][j]:
            for k in range(m):
                rikai[k] += ca[h][k+1]
            tmp += ca[h][0]
        
        flag = True
        for p in rikai:
            if p < x:
                flag = False
        if ans > tmp and flag:
            ans = tmp
            
            
        tmp = 0
        rikai = [0 for i in range(m)]
if ans == pow(10, 1000):
    print(-1)
else:
    print(ans)

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

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


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

ans = float("inf")
for i in range(1 << N):
    tmp = [0] * (M+1)  
    flg = 0
    for j in range(N):
        if (i>>j) & 1:
            for k in range(M+1):
                tmp[k] += text[j][k]
    for l in range(1, M+1):
        if tmp[l] < X:
            flg = 1
            break
    if tmp[0] != 0 and not flg:   
        ans = min(ans, tmp[0])    

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

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

for i in range(2 ** N):
    buy = []
    temp = [0]*(M+1)
    for j in range(N): 
        if ((i >> j) & 1):
            buy.append(C[j][0]) 
            for k in range(M+1):
                temp[k] += C[j][k]
    
    check = 0
    for j in range(1,M+1):
        if temp[j]<X:
            check += 1
    
    if check == 0:
        ans.append(temp[0]) 

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

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



import itertools

result = []
for n in range(1,len(lines)+1):
    for conb in itertools.combinations(lines, n):
        result.append(list(conb)) 

candidates = set()
for r in result:
    
    tmp = [0 for _ in range(M+1)]
    for line in r:
        for i, l in enumerate(line):
            tmp[i] += l
    
    flag_add = True
    for i in range(M):
        if tmp[1+i] < X:
            flag_add = False
            break
    if flag_add:
        candidates.add(tmp[0])

ans = min(candidates) if len(candidates) != 0 else -1
print(ans)

Solution (Python):
n,m,x=map(int,input().split())
a=[]
num=[]
for i in range(n):
    inp=list(map(int,input().split()))
    a.append(inp[1:])
    num.append(inp[0])
ans=10**12
flag=0
for i in range(2**n):
    f=0
    s=0
    cnt=[0]*m
    for j in range(n):
        if (i>>j & 1):
            for k in range(m):
                cnt[k]+=a[j][k]
            s+=num[j]
    for l in range(len(cnt)):
        if cnt[l]<x:
            f=1
    if f==0:
        ans=min(ans,s)
        flag=1
if flag==1:
    print(ans)
else:
    print(-1)

Solution (Python):
from operator import add

ans = 10000000
N, M, X = map(int, input().split())
C = [list(map(int, input().split())) for i in range(N)]
for i in range(2 ** N):
    cnt = 0
    res = [0] * (M + 1)
    for j in range(N):
        if ((i >> j) & 1):
            res = list(map(add, res, C[j]))
    for r in res[1:]:
        if r >= X:
            cnt += 1
    if cnt == len(res[1:]) and ans > res[0]:
        ans = res[0]

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

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

num=[]
for i in range(2 **n):
  chars = list(f"{i:0{n}b}")
  chars=list(map(int,chars))
  num.append(chars)

ans=100000000000000
for cart in num:
    t=[0]*m
    money=0
    for i in range(len(cart)):
        if cart[i]==1:
            money+=c[i]
            for k in range(m):
                t[k]+=a[i][k]
    if min(t)>=x and money<ans:
        ans=money
if ans==100000000000000:
    print(-1)
else:
    print(ans)

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):
N,M,X=list(map(int,input().split()))
cost = []
tech = []
for _ in range(N):
    book=list(map(int,input().split()))
    cost.append(book[0])
    tech.append(book[1:])

ans = 10**10
for i in range(1,2**N):
    tmp = [0]*M
    c = 0
    for ind,j in enumerate("{:0>{haba}b}".format(i, haba=N)):
        if j == "0":
            continue
        c+=cost[ind]
        for k,upp in enumerate(tech[ind]):
            tmp[k]+=upp
    isOk = True
    for t in tmp:
        if t<X:
            isOk = False
            break
    if isOk:
        ans = min(ans,c)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Solution (Python):
import itertools

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

min_money = 10**6 * 12
for num in range(1, n + 1):
    for choices in itertools.combinations(range(n), num):
        is_ok = True
        for j in range(m):
            understand_rate = 0
            for i in choices:
                understand_rate += a[i][j]
            if understand_rate < x:
                is_ok = False
                break
        if is_ok:
            money = 0
            for i in choices:
                money += c[i]
            min_money = min(min_money, money)
if min_money == 10**6 * 12:
    print(-1)
else:
    print(min_money)

Solution (Python):
N,M,X = map(int,input().split())
r = [0]*M
A = []
ans = float('inf')
for _ in range(N):
    A_ = list(map(int,input().split()))
    A.append(A_)
    for i in range(M):
        r[i] += A_[i+1]
for i in range(len(r)):
    if r[i] < X:
        print(-1)
        exit()

for i in range(2**N):
    r = [0]*(M+1)
    p = 0
    for j in range(N):
        if ((i>>j)&1):
            c = A[j]
            for k in range(M+1):
                r[k] += c[k]
    for l in range(M):
        if r[l+1] <X:
            p = -1
            break
        else:
            continue
    if p == 0:
        ans = min(ans,r[0])
    else:
        continue
print(ans)

Solution (Python):

import math

def input_num():
	ls = input().strip().split(" ")
	return [int(e) for e in ls]

n,m,x = input_num()
c_ls = []
a_ls = []
for i in range(n):
	ls = input_num()
	c = ls[0]
	c_ls.append(c)
	a_ls.append(ls[1:])



def judge(tx):
	for i in range(len(tx)):
		if tx[i] < x: return False
	return True

tc_ls = []
for i in range(2**n):
	raw_s = bin(i)[2:]
	s = "0"*(n-len(raw_s)) + raw_s
	f_ls = [e == "1" for e in s]
	tc = 0
	tx = [0 for _ in range(m)]
	for book_idx, f in enumerate(f_ls):
		if f is False: continue
		tc += c_ls[book_idx]
		tx = [tx[j]+a_ls[book_idx][j] for j in range(m)]
	if judge(tx) is True:
		tc_ls.append(tc)

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

Solution (Python):
from itertools import combinations 
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
ans = float("INF")
for a in range(1, n + 1):
    for i in combinations(c, a):
        point = [0] * m
        money = 0
        for j in range(a):
            for k in range(m):
                point[k] += i[j][k + 1]
            money += i[j][0]
        if min(point) >= x:
            ans = min(ans, money)

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

Solution (Python):


N, M, X = map(int, input().split())
C, A = [], []
for _ in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)

costs = []
def f(i, cost, points):
    if X <= min(points):
        costs.append(cost)
        return
    if N <= i:
        return
    f(i + 1, cost, points)
    tmp = [p for p in points]
    for j in range(M):
        tmp[j] += A[i][j]
    f(i + 1, cost + C[i], tmp)

f(0, 0, [0] * M)
print(min(costs) if len(costs) != 0 else -1)

Solution (Python):
import numpy as np
n,m,x = map(int,input().split())
b = []
for _ in range(n):
    c = np.array(list(map(int,input().split())))
    b.append(c)
ans = float('INF')
d = np.array([x]*m)
for i in range(2**n):
    bag = []
    for j in range(n):
        if ((i>>j) & 1):
            bag.append(b[j])
    if bag:
        c = sum(bag)
        e = c[1:] - d
        if all(i >= 0 for i in e):
            ans = min(ans, c[0])
if ans == float('INF'):
    print(-1)
else:
    print(ans)

Solution (Python):
def calc_cost(book_dict, book_list, M, X):
    algo_score = [0] * M
    cost = 0
    for book_index in book_list:
        A = book_dict[book_index][1]
        cost += book_dict[book_index][0]
        for i in range(len(A)):
            algo_score[i] += A[i]
            
    for i in range(M):
        if (algo_score[i] < X):
            return -1
    
    return cost
        
    


def main():
    from itertools import combinations
    N, M, X = map(int, input().split())
    book_dict = {}
    for i in range(N):
        record = list(map(int, input().split()))
        c = 0
        A = []

        for j in range(M+1):
            if (j == 0):
                c = record[j]
            else:
                A.append(record[j])
        book_dict[i] = (c, A)

    max_cost = (10**5) * N + 1
    min_cost = max_cost
    is_possible = False
    for i in range(1, N+1, 1):
        for comb in combinations(list(range(N)), i):
            cost = calc_cost(book_dict, list(comb), M, X)
            if(cost != -1):
                is_possible = True
                min_cost = min(min_cost, cost)

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

main()

Solution (Python):

def _main():
  n_book, n_algo, target = map(int, input().split())

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

  ans = float('inf')
  def dp(cost, current_levels, current_book):
    if min(current_levels) >= target:
      nonlocal ans
      ans = min(ans, cost)
      return
    for index, book_info in enumerate(book_infos[current_book+1:], current_book+1):
      next_levels = [cur + up for cur, up in zip(current_levels, book_info[1:])]
      dp(cost+book_info[0], next_levels, index)

  dp(0, [0 for _ in range(n_algo)], -1)
  print(ans if ans < float('inf') else -1)
  
_main()

Solution (Python):
import numpy as np

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

min_cost = float('inf')
for i in range(2 ** n):
    cost = 0
    _sum = np.array([0] * m)
    for j in range(n):  
        if ((i >> j) & 1):  
            _sum += np.array(books[j][1:]) 
            cost += books[j][0]
    flag = 0
    for k in _sum:
        if k < x:
            flag = 1
    if flag == 0:
        min_cost = min(min_cost, cost)
if min_cost == float('inf'):
    print(-1)
else:
    print(min_cost)

Solution (Python):
import itertools

N, M, X = map(int, input().split())
C = [0 for _ in range(N)]
A = [[] for _ in range(N)]
for i in range(N):
  lis = list(map(int, input().split()))
  C[i] = lis[0]
  A[i] = lis[1:]
  
junretu = list(itertools.product([0, 1], repeat=N))
mini = [10**10]
for jun in junretu:
  count = 0
  und = [0 for _ in range(M)]
  for i, j in enumerate(jun):
    if j == 1:
      count += C[i]
      for k in range(M):
        und[k] += A[i][k]
  flag = 0
  for i in range(M):
    if und[i] >= X:
      continue
    flag = 1
    break
  if flag == 0:
    mini.append(count)
if min(mini) == 10**10:
  print(-1)
else:
  print(min(mini))

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

import itertools

ans = float('inf')
for r in range(n+1):
    for idxs in itertools.combinations(range(n), r=r):
        price = [0]*m
        for idx in idxs:
            for i in range(m):
                price[i] += a[idx][i]
        
        if all(price[i] >= x for i in range(m)):
            ans = min(ans, sum(c[idx] for idx in idxs))

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

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

N,M,X = (int(x) for x in input().split())
CA = np.zeros((N,M+1))
ans = float('inf')
for i in range(N):
    CA[i] = np.array(list(map(int, input().split())))
for i in range(1,N+1):
    for x in combinations(CA,i):
        temp = np.sum(x,axis=0)
        for j in range(1,M+1):
            if temp[j] < X:
                break
        else:
            ans = min(ans,temp[0])
if ans == float('inf'):
    print('-1')
else:
    print(int(ans))

Solution (Python):

from itertools import combinations

n,m,k=[int(i) for i in input().split()]

glob=[]

for i in range(n):
    arr=[int(i) for i in input().split()]
    glob.append(arr)

l=list(range(0,n))

mino=1000000000000000

for i in range(1,n+1):

    comb = combinations(l,i)

    r=[]
    for ijk in range(m+1):
        r.append(0)

    for z in comb:
        for fg in range(m+1):
            r[fg]=0
        for y in z:
            for yu in range(m+1):
                r[yu]+=glob[y][yu]
        if min(r[1:])>=k:
            mino=min(mino,r[0])
if mino==1000000000000000:
    print(-1)
else:
    print(mino)