Problem:
 Score : 300 points    Problem Takahashi, who is a novice in competitive programming, wants to learn M algorithms.
Initially, his understanding level of each of the M algorithms is 0 .  Takahashi is visiting a bookstore, where he finds N books on algorithms.
The i -th book ( 1\leq i\leq N ) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j -th algorithm will increase by A_{i,j} for each j ( 1\leq j\leq M ).
There is no other way to increase the understanding levels of the algorithms.  Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.      Constraints  All values in input are integers.  1\leq N, M\leq 12  1\leq X\leq 10^5  1\leq C_i \leq 10^5  0\leq A_{i, j} \leq 10^5         Input Input is given from Standard Input in the following format:  N  M  X  C_1  A_{1,1}  A_{1,2}  \cdots  A_{1,M}  C_2  A_{2,1}  A_{2,2}  \cdots  A_{2,M}  \vdots  C_N  A_{N,1}  A_{N,2}  \cdots  A_{N,M}       Output If the objective is not achievable, print -1 ; otherwise, print the minimum amount of money needed to achieve it.        Sample Input 1 3 3 10
60 2 2 4
70 8 7 9
50 2 3 9      Sample Output 1 120  Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.       Sample Input 2 3 3 10
100 3 1 4
100 1 5 9
100 2 6 5      Sample Output 2 -1  Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.       Sample Input 3 8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2      Sample Output 3 1067

Solution (Python):



import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


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

    ans = float("inf")
    for bit in range(1 << N):
        S = [0]*(M+1)
        for i, ca in enumerate(CA):
            if (1 << i) & bit == 1 << i:
                S = list(map(sum, zip(S, ca)))
        if min(S[1:]) >= X:
            ans = min(ans, S[0])

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

    print(ans)


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

    b = deque()
    ans = dfs(0, b)
    if ans == float("inf"):
        ans = -1

    print(ans)


def dfs(n, B):
    if n == N:
        S = [0]*(M+1)
        for i, ca in enumerate(CA, 1):
            if i in B:
                S = list(map(sum, zip(S, ca)))
        if min(S[1:]) < X:
            return float("inf")
        else:
            return S[0]

    ans = float("inf")
    B.append(n+1)
    ans = min(ans, dfs(n+1, B))
    B.pop()
    ans = min(ans, dfs(n+1, B))

    return ans


if __name__ == "__main__":
    
    resolve()

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

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

from itertools import combinations

costs =[]
for i in range(1,N+1):
    idx = list(range(N))
    comb = list(combinations(idx,i))
    for c in comb:
        scores = [0]*M
        cost = 0
        for j in c:
            cost += C[j]
            for m in range(M):
                scores[m] += A[j][m]

            check = [int(s>=X) for s in scores]

            if sum(check)==M:
                costs.append(cost)

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

Solution (Python):



import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


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

    ans = float("inf")
    for bit in range(1 << N):
        S = [0]*(M+1)
        for i, ca in enumerate(CA):
            if (1 << i) & bit == 1 << i:
                S = list(map(sum, zip(S, ca)))
        for s in S[1:]:
            if s < X:
                break
        else:
            ans = min(ans, S[0])

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

    print(ans)


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

    b = deque()
    ans = dfs(0, b)
    if ans == float("inf"):
        ans = -1

    print(ans)


def dfs(n, B):
    if n == N:
        S = [0]*(M+1)
        for i, ca in enumerate(CA, 1):
            if i in B:
                S = list(map(sum, zip(S, ca)))
        if min(S[1:]) < X:
            return float("inf")
        else:
            return S[0]

    ans = float("inf")
    B.append(n+1)
    ans = min(ans, dfs(n+1, B))
    B.pop()
    ans = min(ans, dfs(n+1, B))

    return ans


if __name__ == "__main__":
    
    resolve()

Solution (Python):



import sys
from itertools import combinations

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)
comb = [0, 1, 2]

save = []

for choice in range(1, N + 1):
    for comb in combinations(list(range(N)), choice):
        ls = [0 for _ in range(M)]
        for i in comb:
            for m in range(M):
                ls[m] += A[i][m]
            if all(list(map(lambda x: x >= X, ls))):
                save.append(sum([C[_] for _ in comb]))
if save:
    print(min(save))
else:
    print(-1)

Solution (Python):
N, M, X = map(int, input().split())
item = []
ans = []
for i in range(N):
  item.append(list(map(int, input().split())))
for i in range(2**N):
  bag = []
  money = 0
  for j in range(N):
    if ((i>>j) & 1):
      bag.append(item[j])
  if bag == []:
    continue
  total = [0] * M
  for k in bag:
    money += k[0]
    for l in range(1, M+1):
      total[l-1] += k[l]
  if min(total) >= X:
    ans.append(money)
if ans == []:
  print(-1)
else:
  print(min(ans))

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

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

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

Solution (Python):
n,m,x=map(int,input().split())
ca=[]
ans=10**9
for i in range(n):
  tmp=list(map(int,input().split()))
  ca.append(tmp)
for p in range(2**n):
  i_bin = (bin(p)[2:]).zfill(n)
  fl=1
  for i in range(1,m+1):
    ttl=sum([int(i_bin[k])*ca[k][i] for k in range(n)])
    if ttl<x: fl=0
  ansc=sum([int(i_bin[k])*ca[k][0] for k in range(n)])
  if fl and ansc<ans:
    ans=ansc
if ans==10**9: print(-1)
else: print(ans)

Solution (Python):
from itertools import combinations

class Solver:
    def __init__(self, N, M, X, C, A):
        self.N = N
        self.M = M
        self.X = X
        self.C = C
        self.A = A

    def is_achievable(self, A):
        result = [0] * self.M
        for a_row in A:
            for i, a in enumerate(a_row):
                result[i] += a

        for n in result:
            if n < self.X:
                return False
        return True

    def solve(self):
        if not self.is_achievable(self.A):
            print(-1)
            return

        min_cost = 10 ** 10
        index_C = [ i for i in range(N) ]
        for i in range(len(index_C)+1):
            for comb in combinations(index_C, i):
                cur_A = []
                cur_cost = 0
                for i in comb:
                    cur_A.append(self.A[i])
                    cur_cost += C[i]
                if self.is_achievable(cur_A):
                    min_cost = min(min_cost, cur_cost)

        print(min_cost)

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

C = [0] * N
A = []

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

solver = Solver(N, M, X, C, A)
solver.solve()

Solution (Python):
from itertools import combinations

def is_achievable(M, X, A):
    result = [0] * M
    for a_row in A:
        for i, a in enumerate(a_row):
            result[i] += a

    for n in result:
        if n < X:
            return False
    return True

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

    C = [0] * N
    A = []

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

    if not is_achievable(M, X, A):
        print(-1)
        return
    
    index_C = [ i for i in range(N) ]
    min_cost = 10 ** 10
    for i in range(len(index_C)+1):
        for comb in combinations(index_C, i):
            cur_A = []
            cur_cost = 0
            for i in comb:
                cur_A.append(A[i])
                cur_cost += C[i]
            if is_achievable(M, X, cur_A):
                min_cost = min(min_cost, cur_cost)

    print(min_cost)

main()

Solution (Python):
N , M , X = list(map(int, input().split()))
C = []
for _ in range(N):
    C.append(list(map(int, input().split())))
ans = 10**9
for i in range(2**N):
    i_bin = (bin(i)[2:]).zfill(N)
    flag = True
    for j in range(1,M+1):
        tot = sum([ int(i_bin[k])* C[k][j] for k in range(N)])
        if tot < X:
            flag = False
    am = sum([ int(i_bin[k]) * C[k][0] for k in range(N)])
    if flag and am<ans:
        ans = am

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

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


def num2bi(num):
    l = [0] * N
    for i in range(N):
        if num >= 2 ** (N - 1 - i):
            num -= 2 ** (N - 1 - i)
            l[i] = 1
    return l


SUM = [0] * M
A = [[0] * M for _ in range(N)]
C = []
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(M):
        SUM[j] += a[j + 1]
        A[i][j] = a[j + 1]
    C.append(a[0])

ans = sum(C)
if min(SUM) < X:
    ans = -1
else:
    for num in range(2 ** N):
        SUM = [0] * M
        tmp = 0
        for i in range(N):
            if num2bi(num)[i] == 1:
                for j in range(M):
                    SUM[j] += A[i][j]
                tmp += C[i]
        if min(SUM) >= X:
            ans = min(ans, tmp)

print(ans)

Solution (Python):
N, M, X = map(int, input().split())
item = []
ans = []
for i in range(N):
  item.append(list(map(int, input().split())))
for i in range(2**N):
  bag = []
  money = 0
  for j in range(N):
    if ((i>>j) & 1):
      bag.append(item[j])
  if bag == []:
    continue
  total = [0] * M
  for k in bag:
    money += k[0]
    for l in range(1, M+1):
      total[l-1] += k[l]
  if min(total) >= X:
    ans.append(money)
if ans == []:
  print(-1)
else:
  print(min(ans))

Solution (Python):
from itertools import product
[N, M, X] = [int(i) for i in input().split()]
bk = [[int(i) for i in input().split()] for _ in range(N)]

ans = 12*10**5 + 1
for seq in product(range(2), repeat=N):
    S = [0]*(M+1)
    for i in range(N):
       for j in range(M+1):
           S[j] += seq[i]*bk[i][j]     
    if min(S[1:M+1]) >= X:
        ans = min(ans, S[0])

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
INF = 10000000000000
N,M,X = map(int,input().split())

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

ans = INF

for bit in range(1 << N):
    sum = 0
    skill = [0] * M
    for n in range(N):
        if bit & (1 << n):
            for i, s in enumerate(A[n],0):
                skill[i] += s
            sum += C[n]

    flag = True
    for i in range(M):
        if skill[i] < X:
            flag = False
            break
    if flag:
        ans = min(ans,sum)

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

Solution (Python):



import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


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

    ans = float("inf")
    for bit in range(1 << N):
        S = [0]*(M+1)
        for i, ca in enumerate(CA):
            if (1 << i) & bit == 1 << i:
                S = list(map(sum, zip(S, ca)))
        for s in S[1:]:
            if s < X:
                break
        else:
            ans = min(ans, S[0])

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

    print(ans)


if __name__ == "__main__":
    
    resolve()

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

d = []

for i in range(1 << N):
    s = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1:
            
            for k in range(M):
                s[k] += a[j][k+1]
            c += a[j][0]

    

    b = True
    for ii in s:
        if ii < X:
            b = False
    if b:
        d.append(c)

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

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

for i in range(2**n):
    
    a = [0]*m
    price = 0
    for j in range(n):
        
        if ((i >> j) & 1):
            for k in range(m):
                a[k] += c[j][k+1]
            
            price += c[j][0]
    if all(j >= x for j in a):
        ans.append(price)

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

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    n, m, x = map(int, input().split())
    data = np.array(read().split(), np.int64)
    data = data.reshape(n, -1) 
    cost_per_cost = data[:, 0] 
    effect_per_book = data[:, 1:]

    costs = np.zeros(2**n, np.int64)
    
    ability = np.zeros((2**n, m), np.int64)
    for i in range(n):
        costs[1<<i:1<<(i+1)] = costs[:1<<i] + cost_per_cost[i]
        ability[1<<i:1<<(i+1)] = ability[:1<<i] + effect_per_book[i]
    ok = np.all(ability >= x, axis=1)
    res = costs[ok]
    if len(res) == 0:
        print(-1)
    else:
        print(res.min())

if __name__ == '__main__':
    main()

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

from itertools import product
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        books.append(tuple(map(int, input().split())))
    p = tuple(product((0, 1), repeat=n))
    r = float('inf')
    for pe in p:
        effects = [0] * (m + 1)
        for i1 in range(n):
            if pe[i1]:
                for i2 in range(m+1):
                    effects[i2] += books[i1][i2]
        if all([e >= x for e in effects[1:]]):
            r = min(r, effects[0])
    if r == float('inf'):
        print(-1)
    else:
        print(r)

if __name__ == '__main__':
    main()

Solution (Python):
n,m,x = map(int,input().split())
c = list(list(map(int,input().split())) for _ in range(n))
ans = 10**7
for i in range(1<<n):
    mokuhyo = [0]*m
    cost = 0
    for j in range(n):
        if i>>j&1:
            for r in range(m):
                mokuhyo[r] += c[j][r+1]
            cost += c[j][0]
    if all(k>=x for k in mokuhyo):
        ans = min(ans, cost)
print("-1" if ans == 10**7 else ans)

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

for i in range(2**n):
    
    a = [0]*(m+1)
    com = i
    for j in range(n):
        if com >= (2**(n-j-1)):
            com -= 2**(n-j-1)
            for k in range(m+1):
                a[k] += c[j][k]
    price = a[0]
    del a[0]
    if all(a[j]>=x for j in range(m)):
        
        ans.append(price)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Solution (Python):
n,m,x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
prices = []
for i in range(2**n):
  buy = [[] for _ in range(m+1)]
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m+1):
        buy[k].append(c[j][k])
  for k in range(1,m+1):
    if sum(buy[k]) < x:
      break
  else:
    prices.append(sum(buy[0]))
if len(prices) == 0:
  print(-1)
else:
  print(min(prices))

Solution (Python):
import numpy as np

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

cost = float("inf")
for i in range(2**N):
  tmp = np.array([0 for _ in range(M+1)])
  for j in range(N):
    if (i>>j) & 1:
      tmp += np.array(C[j])
  if min(tmp[1:]) >= X:
    cost = min(cost, tmp[0])

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

Solution (Python):
import itertools
n, m, x = map(int, input().split())
books = []
for i in range(n):
  ins = list(map(int, input().split()))
  books.append({"c": ins[0], "a": ins[1: m+1]})
ans = float('inf')
for i in range(1, n+1):
  book_list = list(itertools.combinations(list(range(n)), i))
  for lis in book_list:
    cost_sum = 0
    a_sum = [0] * m
    ok = 0
    ok_list = [False] * m
    for j in lis:
      cost_sum += books[j]['c']
      for k in range(m):
        a_sum[k] += books[j]['a'][k]
        if not ok_list[k] and a_sum[k] >= x:
          ok += 1
          ok_list[k] = True
    if ok == m and ans > cost_sum:
      ans = cost_sum
if ans == float('inf'):
  print(-1)
else:
  print(ans)

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

li=[]
ans=100000000000000000000000000000000

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

for k in range(2**N):
    temp=0
    skill=[0]*M
    k=str(bin(k))
    k=k[2:]
    while len(k)!=N:
        k="0"+k
    for l in range(N):
        if k[l]=="1":
            temp+=li[l][0]
            for m in range(1,M+1):
                skill[m-1]+=li[l][m]
    if min(skill)>=X:
        if ans>temp:
            ans=temp
if ans==100000000000000000000000000000000:
    print(-1)
else:
    print(ans)

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



INF = 10**10
min_cost = INF

for b in range(2**N): 
    
    
    
    
    cost = 0 
    algo_level = [0] * M 
    for i in range(N): 
        
        
        if(b >> i & 1): 
            
            
            cost += C[i]
            for a in range(M): 
                algo_level[a] += A[i][a]
    if(min(algo_level) >= X): 
        min_cost = min(cost, min_cost)

if(min_cost < INF):
    print(min_cost)
else:
    print('-1')

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

ans = 10 ** 10
for i in range(2 ** N):
    v = [0 for _ in range(M)]
    c = 0
    for j in range(N):
        if i & 1 << j:
            for k, a in enumerate(A[j]):
                v[k] += a
            c += C[j]
    if min(v) >= X:
        ans = min(ans, c)

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

Solution (Python):
def main():
    n, m, x = map(int, input().split())
    book_list = [list(map(int, input().split())) for _ in range(n)]
    ans = 12 * 10 ** 5 + 1

    for i in range(2 ** n):
        money = 0
        level = [0] * m
        for j in range(n):
            if (i >> j) & 1:
                money += book_list[j][0]
                for k in range(m):
                    level[k] += book_list[j][k + 1]
        for j in range(m):
            if level[j] < x:
                break
        else:
            ans = min(ans, money)

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


if __name__ == "__main__":
    main()

Solution (Python):
N, M, X = map(int, input().split(' '))
A, C = [], []
for n in range(N):
  inp = list(map(int, input().split(' ')))
  C.append(inp[0])
  A.append(inp[1:])
  
def proceed_step(remained, current_cost, n):
  global N, X
  remained_next = []
  
  if not remained: return current_cost
  if n == N: return float('inf')
  
  for algorithm in remained:
    m, current_sum = algorithm[0], algorithm[1]
    current_sum += A[n][m]
    if current_sum < X:
      remained_next.append([m, current_sum])
      
  return min(proceed_step(remained, current_cost, n+1),
             proceed_step(remained_next, current_cost + C[n], n+1))

remained = [[m, 0] for m in range(M)]
total_cost = proceed_step(remained, current_cost=0, n=0)
if total_cost == float('inf'): print(-1)
else: print(total_cost)

Solution (Python):
from itertools import product

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

ans = 10 ** 5 * n
flag = False
for i in product([0,1], repeat=n):
    price = 0
    skill = [0] * m
    for index_, bit in enumerate(i):
        if bit:
            for j in range(m):
                skill[j] += book[index_][ j + 1]
            price += book[index_][0]
    if all(v >= x for v in skill):
        ans = min(ans, price)
        flag = True
if flag:
    print(ans)
else:
    print(-1)

Solution (Python):
N,M,X = map(int,input().split())
a = [list(map(int,input().split())) for i in range(N)]
d = []
for i in range(2**N):
    b = [0] * (M+1)
    e = i
    for j in range(N):
        if e >= (2**(N-j-1)) :
            e -= (2**(N-j-1))
            for k in range(M+1):
                b[k] += a[j][k]
    c = 1
    for j in range(1,M+1):
        if b[j] < X:
            c = 0
            break
    if c == 1:
        d.append(b[0])
if len(d) > 0:
    ans = min(d)
else:
    ans = -1
print(ans)

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

C = []
A = []

for _ in range(N):
    q = list(map(int, input().split()))

    C.append(q[0])
    A.append(q[1:])



ans = 1300000

for bit in range(1 << N):
    acquire = [0] * M
    cost = 0
    for i in range(N):
        if (bit >> i) % 2 == 1:
            cost += C[i]
            acquire = [a + b for a, b in zip(acquire, A[i])]

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

if ans == 1300000:
    ans = -1

print(ans)

Solution (Python):
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 = -1
for i in range((1<<N)):
    u = [0] * M
    p = 0
    for j in range(N):
        if i & (1 << j):
            p += C[j]
            for k in range(M):
                u[k] += A[j][k]
    if min(u) >= X:
        if ans == -1 or ans > p:
            ans = p
print(ans)

Solution (Python):
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 = -1
for i in range((1<<N)):
    u = [0] * M
    p = 0
    for j in range(N):
        if i & (1 << j):
            p += C[j]
            for k in range(M):
                u[k] += A[j][k]
    if min(u) >= X:
        if ans == -1 or ans > p:
            ans = p
print(ans)

Solution (Python):
nb,na,level = map(int , input().split())
blevels = []
for i in range(nb):
    blevels.append(list(map(int , input().split())))
ans = float('inf')

for i in range(1,2**nb):
    flag = 0
    levels_sum = [0]*na
    price_sum = 0
    for j in range(nb):
        if((1<<j) & i > 0):
            price_sum += blevels[j][0]
            for k in range(1,na+1):
                levels_sum[k-1] += blevels[j][k]
    
    
    for levels in levels_sum:
        if(levels < level):
         
            flag = 1
            break
    if(flag == 0 and ans > price_sum):
        ans = price_sum
        
if(ans != float('inf')):
    print(ans)
else:
    print("-1")

Solution (Python):
import itertools as it

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

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
    
    bag = [0] * (M+1)
    for i in range(N):
        if comb[i] == 0:
            continue
        else:
            for j in range(M+1):
                bag[j] += book[i][j]

    if min(bag[1:]) < X:
        continue
    else:
        prices.append(bag[0])

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

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

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



ans = 10 ** 8
for i in range(2**n):

    skill = [0] * m
    price = 0
    count = 0
    for k in range(n):
        if (i >> k) & 1:

            price += array[k][0]
            for j in range(m):
                skill[j] += array[k][j+1]
    for l in range(m):
        if skill[l] < x:
            break
        else:
            count += 1
    if count == m:
        ans = min(ans, price)

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

Solution (Python):
import itertools as it

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

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
	bag = [0] * (M+1)
	for i in range(N):
		if comb[i] == 0:
			continue
		else:
			for j in range(M+1):
				bag[j]+=book[i][j]
	if min(bag[1:]) < X:
		continue
	else:
		prices.append(bag[0])

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

Solution (Python):
import itertools as it
N, M, X = map(int, input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
    
    bag = [0] * (M + 1)
    for i in range(N):
        if comb[i] == 0:
            continue
        else:
            for j in range(M + 1):
                bag[j] += book[i][j]
    
    if min(bag[1:]) < X:
        continue
    else:
        prices.append(bag[0])
if len(prices) == 0:
    print(-1)
else:
    print(min(prices))

Solution (Python):
import itertools as it

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

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
	bag = [0] * (M+1)
	for i in range(N):
		if comb[i] == 0:
			continue
		else:
			for j in range(M+1):
				bag[j]+=book[i][j]
	if min(bag[1:]) < X:
		continue
	else:
		prices.append(bag[0])

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

Solution (Python):

import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]

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

    inf = 10**18

    
    
    ans = inf
    for i in product([0,1], repeat=N):
        ok = True
        for m in range(1, M + 1):
            s = 0
            for n in range(N):
                if i[n] == 1:
                    s += A[n][m]
            if s < X:
                ok = False
                break
        if ok:
            money = 0
            for n in range(N):
                if i[n] == 1:
                    money += A[n][0]
            ans = min(ans, money)

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]

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

    inf = 10**18

    
    
    ans = inf
    for i in product([0,1], repeat=N):
        ok = True
        for m in range(1, M + 1):
            s = 0
            for n in range(N):
                if i[n] == 1:
                    s += A[n][m]
            if s < X:
                ok = False
        if ok:
            money = 0
            for n in range(N):
                if i[n] == 1:
                    money += A[n][0]
            ans = min(ans, money)

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from itertools import product
def input():
    return sys.stdin.readline()[:-1]

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

    for m in range(1, M + 1):
        s = 0
        for n in range(N):
            s += A[n][m]
        if s < X:
            print(-1)
            exit()

    
    
    ans = 10 ** 15
    for i in product([0,1], repeat=N):
        c = 0
        for m in range(1, M + 1):
            s = 0
            for n in range(N):
                if i[n] == 1:
                    s += A[n][m]
            if s >= X:
                c += 1
        if c == M:
            money = 0
            for n in range(N):
                if i[n] == 1:
                    money += A[n][0]
            ans = min(ans, money)
    print(ans)

if __name__ == '__main__':
    main()