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 = [0] * n
a = []
for i in range(n):
    ca = list(map(int, input().split()))
    c[i] = ca[0]
    a.append(ca[1:])

ans = 10**7
for bit in range(1<<n):
    cost = 0
    ex = [0] * m
    for i in range(n):
        if bit & (1<<i):
            cost += c[i]
            for j in range(m):
                ex[j] += a[i][j]

    f = True
    for i in range(m):
        if ex[i] < x:
            f = False
            break
    if f:
        ans = min(ans, cost)

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

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

ans = float("inf")
for i in range(1<<n):
    t = [0] * m
    cost = 0
    for j in range(n):
        if i & (1<<j):
            cost += c[j]
            for k in range(m):
                t[k] += a[j][k]
    if min(t) >= x:
        ans = min(ans, cost)

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

Solution (Python):
*o, = open(0)

import numpy as np

(n, m, x), *ca = map(lambda x: np.array(list(map(int, x.split()))), o)

INF = 1 << 31

ans = INF

for i in range(2**n):
    tmp = np.zeros(m+1, int)
    sel = []
    for j, dig in enumerate(bin(i)[2:][::-1]):
        if int(dig):
            tmp += ca[j]
            sel.append(j)
    if min(tmp[1:]) >= x:
        ans = min(ans, tmp[0])
        

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

Solution (Python):
import sys
from itertools import combinations, chain
from operator import itemgetter
from functools import reduce

n, m, x = map(int, next(sys.stdin).split())
books = [tuple(map(int, s.split())) for s in sys.stdin]

book_combinations = chain.from_iterable(combinations(books, i)
                                        
                                        
                                        for i in range(1, n + 1))

def total_price(book_list, _price_getter=itemgetter(0)):
  return sum(map(_price_getter, book_list))
def min_score(book_list, _score_getter=itemgetter(slice(1, None))):
  book_scores = map(_score_getter, book_list)
  scores = [0] * m
  for book_score in book_scores:
    for i, score in enumerate(book_score):
      scores[i] += score
  return min(scores)

price_score_list = ((total_price(book_list), min_score(book_list))
                    for book_list in book_combinations)
prices = (price for price, score in price_score_list if score >= x)
answer = min(prices, default=-1)
print(answer)

Solution (Python):
import numpy as np

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

ans = 9999999999
for i in range(2 ** n):
    p = np.zeros(m)
    csum = 0
    for j in range(n):
        if i & (2 ** j):
            p += a[j]
            csum += c[j]
    if np.amin(p) >= x and csum < ans:
        ans = csum
if ans == 9999999999:
    print(-1)
else:
    print(ans)

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

def calc_price(bit):
  price_total = 0
  learn_total = [0]*m
  
  for i in range(n):
    if (bit >> i) & 1:
      price_total += c[i]
      learn = a[i]
      for j, la in enumerate(learn):
        learn_total[j] += la
  
  if check(learn_total):
    return price_total
  else:
    return INF
  
def check(learn_total):
  for i in range(m):
    if learn_total[i] < x:
      return False
  return True
    
for i in range(n):
  c_temp, *a_temp = list(map(int, input().split()))
  c.append(c_temp)
  a.append(a_temp)
  
INF = float("inf")
ans = INF

for bit in range(1 << n):
  price = calc_price(bit)
  ans = min(ans, price)
  
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):



MAX = 100000000000
def resolve():
    N,M,X = map(int,input().split())
    A,C = [],[]
    for _ in range(N):
        c_a = list(map(int, input().split()))
        c = c_a.pop(0)
        A.append(c_a)
        C.append(c)
    
    def func(cost,a,i):
        if min(a) >= X:
            return cost
        elif i == N:
            return MAX
        total_A = [x+y for (x,y) in zip(a,A[i])]
        
        return min(func(cost + C[i],total_A,i+1),func(cost,a,i+1))

    ans = func(0,[0]*M,0) 
    if ans == MAX:
        print(-1)
    else:
        print(ans)
resolve()

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

ans = float("inf")
for i in range(2**n):
    tmp = 0
    A = [0] * m
    for j in range(n):
        if i & 2**j:
            tmp += BOOKS[j][0]
            for k in range(m):
                A[k] += BOOKS[j][k + 1]
    flag = True
    for a in A:
        if a < x:
            flag = False
    if flag:
        ans = min(ans, tmp)

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

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

ans = []
for i in range(1, 2**N):
    tmp = []
    pnt = 0
    for j in range(N):
        if i>>j & 1 == 1:
            tmp.append(A[j])
            pnt += C[j]
    *score, = map(sum, zip(*tmp))
    if min(score) >= X:
        ans.append(pnt)

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

Solution (Python):
import sys





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


ret = sys.maxsize
for i in range(2**n):
    _cost = 0
    _know = [0] * m
    for j in range(n):
        if i & (1 << j):
            for k in range(m):
                _know[k] += arr[j][1+k]
            _cost += arr[j][0]

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

    if flag and ret > _cost:
        ret = _cost

if ret == sys.maxsize:
    ret = -1

print("{}".format(ret))

Solution (Python):
from itertools import product
n,m,x = map(int,input().split())
books = [list(map(int,input().split())) for i in range(n)]
costs = []
skills = []
for book in books:
    costs.append(book[0])
    skills.append(book[1:])

ans = float('inf')

for bit in product((0,1),repeat=n):
    
    current_cost = 0
    current_skill = [0] * m
    for i in range(n):
        if bit[i] == 1:
            for j in range(m):
                current_skill[j] += skills[i][j]
                
            current_cost += costs[i]


    if x <= min(current_skill):
        ans = min(ans,current_cost)


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

Solution (Python):
import numpy as np
import sys
n,m,x = map(int,input().split())
input_list = [np.array(list(map(int,input().split()))) for _ in range(n)]
temp_fee = sys.maxsize
for i in range(2**n):
    list2 = [np.array([0]*(m+1))]
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(input_list[j])
    list3 = sum(list2)
    if min(list3[1:])>=x and list3[0]<temp_fee:
        temp_fee = list3[0]
if temp_fee != sys.maxsize:
    print(temp_fee)
else:
    print(-1)

Solution (Python):
def check(learn_total):
  for i in range(m):
    if learn_total[i] < x:
      return False
  return True

def calc_price(bit):
  price_total = 0
  learn_total = [0] * m 

  for i in range(n):
    if (bit >> i) & 1:  
      price_total += c[i]  
      learn = a[i]  
      for j, la in enumerate(learn):
        learn_total[j] += la

  if check(learn_total):
    return price_total
  else:
    return INF 
  
  
if __name__ == '__main__':
  n, m, x = list(map(int, input().split()))
  c = []
  a = [] 

  for i in range(n):
    c_temp, *a_temp = list(map(int, input().split()))
    c.append(c_temp)
    a.append(a_temp)

  INF = float("inf")
  ans = INF

  for bit in range(1 << n):
    price = calc_price(bit)
    ans = min(ans, price) 

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

Solution (Python):
from collections import deque

n, m, x = map(int, input().split())
c = deque()
a = deque()
ans = float("inf")

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

for i in range(2**n):
    t = 0
    score = [0]*m
    for j in range(n):
        if i&(2**j) > 0:
            t += c[j]
            for k in range(m):
                score[k] += a[j][k]
    if min(score) >= x:
        ans = min(ans, t)

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

Solution (Python):
n, m, x = list(map(int, input().split()))
c = [0] * n
a = [[]  for _ in range(n)]
INF = float('inf')
ans = INF

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

for s in range(1<<n):
    smart = [0] * m
    cost = 0
    for i in range(n):
        if not(s>>i & 1):continue
        cost += c[i]
        for j in range(m):
            smart[j] += a[i][j]

    flg = True
    for i in range(m):
        if smart[i] < x:
            flg = False
    if flg:
        ans = min(ans, cost)
if ans == INF:
    print(-1)
else: print(ans)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(100000)

def dfs(cost, i, ratio):
    if i == n:
        global ans
        if cost < ans and all([r >= x for r in ratio]):
            ans = cost
        return
    dfs(cost, i+1, ratio)
    dfs(cost+c[i], i+1, ratio+a[i])

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c = [None]*n
    a = np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**8
    dfs(0, 0, np.array([0]*m))
    if ans == 10**8:
        print(-1)
    else:
        print(ans)

Solution (Python):
from itertools import combinations
n,m,x=[int(i) for i in input().split()]
a=[]
for i in range(n):
    a.append([int(i) for i in input().split()])
cost=[]
for i in range(1,n+1):
    c=list(combinations(a,i))
    b=[[0]*(m+1) for i in range(len(c))]
    for k in range(len(c)):
        for j in range(len(c[k])):
            for i in range(m+1):
                b[k][i]+=c[k][j][i]
    for i in range(len(b)):
        s=0 ; flag=0
        for j in range(1,len(b[i])):
            if b[i][j]<x:
                flag=1
                break
        if flag==0: 
            cost.append(b[i][0])
if not cost: print(-1)
else: print(min(cost))

Solution (Python):
from itertools import product

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 = 10**9

for bit in product((0, 1), repeat=N):
    cost = 0
    study = [0] * M
    for i in range(N):
        if bit[i]:
            for m in range(M):
                study[m] += A[i][m]
            cost += C[i]

    if min(study) >= X: 
        ans = min(ans, cost)

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

Solution (Python):
N, M, X = map(int, input().split())
C = [0] * N
A = []

for __ in range(N):
    nums = list(map(int, input().split()))
    C[__] = nums[0]
    A.append(nums[1:])

mincost = 10e9
ok = False
for i in range(1 << N):
    cost = 0
    skill = [0] * M

    for u in range(N):
        if i & (1<<u):
            cost += C[u]
            for si, s in enumerate(A[u]):
                skill[si] += s
    
    
    if all([s >= X for s in skill]):
        ok = True
        if mincost > cost:
            mincost = cost

print(mincost if ok else -1)

Solution (Python):
import itertools

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

c = []
a = []
calc = [0] * m


for cai in ca:
  tmp = list(map(int,cai.split()))
  c.append(tmp[0])
  a.append(tmp[1:])

ite = itertools.product(range(2), repeat=n)
ans = float('inf')
tmp = 0
k = 0
for i in ite:
  calc = [0] * m
  tmp = 0
  for j in range(n):
    if i[j] == 1 :
      tmp += c[j]
      for k in range(m):
        calc[k] += a[j][k] 
  if len([z for z in calc if z >= x]) == m:
    ans = min(ans,tmp)

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

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

ans = 10**9
for i in range(1, n+1):
  for j in combinations(ca, i):
    t = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        t[l] += k[l]
    if all(t[q] >= x for q in range(1,m+1)):
      ans = min(ans, t[0])
if ans != 10**9: print(ans)
else: print(-1)

Solution (Python):
n, m, x=map(int, input().split())
c=[]
a=[]
for i in range(n):
  l=list(map(int, input().split()))
  c.append(l[0])
  a.append(l[1:])
import numpy as np
ab=np.array(a).T

ans=[]


from itertools import product
s = [0,1]
for i in sorted(list(product(s, repeat=n))):
  for t in ab:
    if sum(np.array(t)*np.array(i))<x:
      break
  else:
    ans.append(sum(np.array(i)*np.array(c)))
    continue
if ans==[]:
  print(-1)
else:
  print(min(ans))

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

nums = []

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

ans = 10000000000


for i in range(2**N):

    money = 0
    skill_point = [0]*M
    goal = [0]*M
    buy = []

    for k in range(N):
        if i>>k & 1:
            buy.append(nums[k])

    for d in buy:
        money += d[0]
        for e in range(M):
            skill_point[e] += d[e+1]

    for f in range(M):
        if skill_point[f] >= X:
            goal[f] = 1

    
    if (0 not in goal) and (money < ans) :
        ans = money

    

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

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

nums = []

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

ans = 10000000000


for i in range(2**N):

    money = 0
    skill_point = [0]*M
    goal = [0]*M
    buy = []
    

    for k in range(N):
        if i>>k & 1:
            buy.append(nums[k])

    for d in buy:
        money += d[0]
        for e in range(M):
            skill_point[e] += d[e+1]

    for f in range(M):
        if skill_point[f] >= X:
            goal[f] = 1

    
    if (0 not in goal) and (money < ans) :
        ans = money

    

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

Solution (Python):


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

INF = 100000000001
ans = INF

for i in range(2**n):
    price = 0
    level = [0]*m
    for j in range(n):
        if  ((i >> j) & 1):
            for k in range(m):
                level[k] += a[j][k]
            price += c[j]
    if min(level) >= x and price <= ans:
        ans = price

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

Solution (Python):
import numpy as np

n, m, x = map(int, input().split())
cost_list = []
matrix = []

for _ in range(n):
  tmp = list(map(int, input().split()))
  matrix.append(tmp)

list_ = []
for i in range(2**n):
  check_list = [0 for _ in range(n)]
  cnt=0
  while True:
    check_list[cnt] = i%2
    i //= 2
    cnt+=1
    if i==0:
      break
  list_.append(check_list)

ans = 100000000000000
for check in list_:
  ans_list = np.zeros(m+1)
  for i, v in enumerate(check):
    if v==1:
      ans_list += np.array(matrix[i])


  flg = True
  for value in ans_list[1:]:
    if value<x:
      flg=False
  if flg:
    ans = min(ans,ans_list[0])

if ans == 100000000000000:
  ans = -1
print(int(ans))

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m,x=nii()
l=[lnii() for i in range(n)]

ans=10**9
for i in range(2**n):
  ml=[0 for j in range(m)]
  use=[0 for i in range(n)]

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

  t_ans=0
  for j in range(n):
    if use[j]==1:
      use_book=l[j]
      t_ans+=use_book[0]
      for k in range(1,m+1):
        ml[k-1]+=use_book[k]

  if min(ml)>=x:
    ans=min(ans,t_ans)

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

Solution (Python):
import sys
 
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)
 
def main():
    import numpy as np
    from itertools import product
 
    n, m, x = list(map(int, readline().split()))
    a, c = [], []
    for i in range(n):
        c_temp, *a_temp = list(map(int, readline().split()))
        c.append(c_temp)
        a.append(a_temp)
 
    a = np.array(a)
    ans = INF
 
    for bit in product(range(2), repeat=n):
        price_total = 0
        learn_total = np.array([0] * m)
        for i in range(n):
            if bit[i] == 1:
                price_total += c[i]
                learn_total += a[i]
        if np.all(learn_total >= x):
            ans = min(ans, price_total)
 
    if ans == INF:
        print(-1)
    else:
        print(ans)
 
 
if __name__ == '__main__':
    main()

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

def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

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

m = 1e9
for i in range(2 ** N):
	total = [0] * (M+1)
	for j in range(N):
		if((i >> j) & 1):
			total = python_list_add(total, A[j])
	if(all(elem >= X for elem in total[1:])):
		m = min(total[0],m)
if m == 1e9:
	m = -1
print(m)

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

ans = float("inf")

for i in range(1<<n):
    cost = 0
    points = [0] * m
    for j in range(n):
        if i>>j & 1:
            cost += L[j][0]
            for k in range(m):
                points[k] += L[j][k+1]

    if min(points) >= x:
        ans = min(ans, cost)

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

else:
    print(ans)

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

states = []
for i in range(n):
    ca = list(map(int, input().split()))
    state = {"cost" : ca[0], "value" :ca[1:]}
    states.append(state)

def check(uselist : list):
    understandings = [0]*m
    cost = 0
    for i, islist in enumerate(uselist):
        if islist == 1:
            for j in range(m):
                understandings[j] += states[i]["value"][j]
            cost += states[i]["cost"]

    for i in range(m):
        if understandings[i] < x:
            return 1000000000
    return cost

ans = 1000000000

for uselist in itertools.product(range(2), repeat=n):
    ans = min(ans, check(uselist))

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

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

for _ in range(n):
    c, *a = map(int, input().split())
    cl.append(c)
    al.append(a)

ans = float('inf')
for i in range(2 ** n):
    sum = 0
    l = [0] * m

    for j in range(n):
        if i >> j & 1:
            sum += cl[j]
            for k in range(m):
                l[k] += al[j][k]

    flg = all([e >= x for e in l])

    if flg:
        ans = min(ans, sum)

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

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

for _ in range(n):
    c, *a = map(int, input().split())
    cl.append(c)
    al.append(a)

ans = float('inf')
for i in range(2 ** n):
    sum = 0
    l = [0] * m
    flg = False

    for j in range(n):
        if i >> j & 1:
            sum += cl[j]
            for k in range(m):
                l[k] += al[j][k]

    for e in l:
        if e < x:
            flg = True
            break

    if not flg:
        ans = min(ans, sum)

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

Solution (Python):
from itertools import product

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

states = []

for i in range(n):
    tmp = list(map(int, input().split()))
    state = {
        'cost': tmp[0],
        'value': tmp[1:]
    }
    states.append(state)


def check(use_list : list):
    gain = [0 for _ in range(m)]
    cost = 0
    for i, is_use in enumerate(use_list):
        if is_use:
            for j in range(m):
                gain[j] += states[i]['value'][j]
            cost += states[i]['cost']

    for j in range(m):
        if gain[j] < x:
            return 1000000000
    return cost

ans = 1000000000

for use_list in product(range(2), repeat=n):
    ans = min(ans, check(use_list))
if ans == 1000000000:
    ans = -1
print(ans)

Solution (Python):

from itertools import product
n, m, x = map(int, input().split())
c = []
a = []
for o in range(n):
    _ = list(map(int, input().split()))
    c.append(_[0])
    a.append(_[1:])
ans = 10**100
for p in product([0, 1], repeat=n):
    skill = [0] * m
    cost = 0
    for i in range(n):
        if p[i]:
            for j in range(m):
                skill[j] += a[i][j]
            cost += c[i]
    if min(skill) >= x:
        ans = min(ans, cost)
if ans == 10**100:
    print(-1)
else:
    print(ans)

Solution (Python):


import itertools

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

prices = []
abilities = []


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

combinations = []


for i in range(1, len(abilities)+1):
    s = list(itertools.combinations(abilities, i))
    combinations.append(s)





for combs in combinations:
    
    for i in range(len(combs)):
        counts = [0] * m
        price = 0

        comb = combs[i]
        
        
        
        for j in range(len(comb)):
            
            a = comb[j]
            price += a[0]

            
            b = a[1:]

            
            for k in range(m):
                counts[k] += b[k]
            
            
            
            ans = ['ok' for num in counts if num >= x]
            if len(ans) == m:
                
                prices.append(price)


if len(prices) >= 1:
    print(min(prices))
else:
    print(-1)

Solution (Python):
N,M,X=[int(i) for i in input().split()]
C=[0]*N
A=[[] for i in range(N)]
for n in range(N):
    tmp=[int(i) for i in input().split()]
    C[n]=tmp[0]
    A[n]=tmp[1:]
Cmin=100000000000
minW=Cmin
for i in range(2**N):
    W=0
    T=[0]*M
    I=i
    cnt=0
    while I>0:
        if I%2==1:
            W+=C[cnt]
            T=[T[j]+A[cnt][j] for j in range(M)]
        cnt+=1
        I//=2
    if X<=min(T) and minW>W:
        minW=W
print(minW if minW!=Cmin else -1)

Solution (Python):
from itertools import combinations as Comb
N, M, X = map(int, input().split())
AC = [""] * N

for c in range(N):
    AC[c] = list(map(int, input().split()))

ans = 12 * 1000000
C = 0

def han(i): 
    global going, C
    A_wa = [0] * M
    for c in i:
        for co in range(1, M + 1, 1):
            A_wa[co - 1] += c[co]
        C += c[0]
    if min(A_wa) >= X:
        going = True
        

for c in range(1, N + 1, 1):
    lll = list(Comb(AC, c))
    for z in lll:
        going = False
        C = 0
        han(z)
        if going and C < ans:
            ans = C
if ans != 12 * 1000000:
    print(ans)
else:
    print(-1)

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

MAX = 10**5 * N + 1
minprice = MAX
for b in range(2**N):
    price = 0
    abilitylist = [0]*(M+1)
    for i in range(1,N+1):
        if b >> (i-1) & 1 == 1:
            price += C[i]
            abilitylist = [x + y for x,y in zip(abilitylist, A[i])]
    
    flag = True
    for ability in abilitylist[1:]:
        if ability < X:
            flag = False
            break
    
    if flag:
        minprice = min(minprice, price)

ans = minprice if minprice != MAX else -1
print(ans)

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

min_money = 1e10
for i in range(2**N):
    buy_list = [0] * N
    skill = [0] * M
    money = 0
    
    for j in range(N):
        if i % 2 == 0:
            buy_list[j] = 1
        i //= 2
    for buy_idx, ca in enumerate(c_a_list):
        if buy_list[buy_idx] == 1:
            for a_idx, a in enumerate(ca[1:]):
                skill[a_idx] += a
            money += ca[0]
    for s_idx, s in enumerate(skill):
        if s < X:
            break
        if s_idx == M-1:
            min_money = min(min_money, money)
if min_money == 1e10:
    print(-1)
else:
    print(min_money)

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

ans = 10**10
for i in range(1<<n):
    li = []
    
    cost = 0
    for j in range(n):
        if (i>>j)&1:
            li.append(score[j])
            cost +=pr[j]

    score_all = [0 for l in range(m)]
    for k in range(len(li)):
        for j in range(m):
            score_all[j] +=li[k][j]
    if all([y>=x for y in score_all]):
        ans = min(ans,cost)

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

Solution (Python):
if __name__ == '__main__':
    n, m, x = list(map(int, input().split()))
    
    c = []
    a = []
    
    def calc_price(bit):
        price_total = 0
        learn_total = [0] * m 
        
        for i in range(n):
            if (bit >> i) & 1:
                price_total += c[i]
                learn = a[i]
                for j, la in enumerate(learn):
                    learn_total[j] += la
        
        if check(learn_total):
            return price_total
        else:
            return INF
        
    def check(learn_total):
        for i in range(m):
            if learn_total[i] < x:
                return False
        return True
    
    for i in range(n):
        c_temp, *a_temp = list(map(int, input().split()))
        c.append(c_temp)
        a.append(a_temp)
        
    INF = float("inf")
    ans = INF
    
    for bit in range(1 << n):
        price = calc_price(bit)
        ans = min(ans, price)
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

Solution (Python):
if __name__ == '__main__':
    n, m, x = list(map(int, input().split()))
    
    c = []
    a = []
    
    def calc_price(bit):
        price_total = 0
        learn_total = [0] * m 
        
        for i in range(n):
            if (bit >> i) & 1:
                price_total += c[i]
                learn = a[i]
                for j, la in enumerate(learn):
                    learn_total[j] += la
        
        if check(learn_total):
            return price_total
        else:
            return INF
        
    def check(learn_total):
        for i in range(m):
            if learn_total[i] < x:
                return False
        return True
    
    for i in range(n):
        c_temp, *a_temp = list(map(int, input().split()))
        c.append(c_temp)
        a.append(a_temp)
        
    INF = float("inf")
    ans = INF
    
    for bit in range(1 << n):
        price = calc_price(bit)
        ans = min(ans, price)
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

Solution (Python):
import itertools

n, m, x = map(int, input().split())
a = []
c = []
for i in range(n):
    line = list(map(int, input().split()))
    c.append(line[0])
    line.pop(0)
    a.append(line)
p = list(map(list, list(itertools.product([0,1], repeat=n))))
flag = 1
min_money = 10**10
for pattern in p:
    flag_1 = 0
    alg = [0 for i in range(m)]
    money = 0
    for i in range(n):
        if pattern[i]:
            money += c[i]
            for j in range(m):
                alg[j] += a[i][j]
    for i in range(m):
        if alg[i] < x:
            flag_1 = 1
    if flag_1:
        continue
    min_money = min(money, min_money)
    flag = 0
if flag:
    print(-1)
else:
    print(min_money)

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

    skill = [0]*M
    get_skill = [0]*M
    money = 0

    ans = 99999999
    back = []

    for i in range(2**N):
        
        for j in range(N):
            if ( (i>>j)&1 ):
                back.append(book[j])
        

        for A in back:
            
            money += A[0]
            for j in range(1,M+1):
                skill[j-1] += A[j]

        

        for k in range(M):
            if skill[k] >= X:
                get_skill[k] += 1

        if 0 not in get_skill:
            if money < ans:
                ans = money

        skill = [0]*M
        get_skill = [0]*M
        money = 0
        back = []

    if ans == 99999999:
        ans = -1
        return ans
    else:
        return ans

print(main())

Solution (Python):
from operator import add
N, M, X = map(int, input().split())


def toBook(line):
    xs = line.split()
    cost = int(xs[0])
    values = list(map(int, xs[1:]))
    return (cost, values)


Books = [toBook(input()) for i in range(N)]
maxCost = 10 ** 15


def isSatisfied(xs):
    return all([x >= X for x in xs])


def rec(i, proficiency, totalCost):
    if i == N:
        if isSatisfied(proficiency):
            return totalCost
        else:
            return maxCost
    else:
        _proficiency = list(map(add, proficiency, Books[i][1]))
        _totalCost = totalCost + Books[i][0]
        cost1 = rec(i + 1, proficiency, totalCost)
        cost2 = rec(i + 1, _proficiency, _totalCost)
        return min(cost1, cost2)


cost = rec(0, [0] * M, 0)
if cost == maxCost:
    print("-1")
else:
    print(cost)

Solution (Python):
N, M, X = map(int, input().split())
Xlist = []
ans = -1
for i in range(N):
    Nlist = list(map(int, input().split()))
    for j in range(len(Xlist)):
        sumList = [x + y for (x, y) in zip(Nlist, Xlist[j])]
        Xlist.append(sumList)
        if min(sumList[1:]) >= X:
            if ans == -1:
                ans = sumList[0]
            elif ans > sumList[0]:
                ans = sumList[0]
    Xlist.append(Nlist)
    if min(Nlist[1:]) >= X:
        if ans == -1:
            ans = Nlist[0]
        elif ans > Nlist[0]:
            ans = Nlist[0]

print(ans)