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.

Submission attempts (in order):
from itertools import combinations
from collections import defaultdict
N, M , X = map(int, input().split())
C = [0 for i in range(N)]
D = defaultdict(list)
ans = 12345678

for i in range(N):
    temp = list(map(lambda x:int(x), input().split()))
    C[i] = temp[0]
    D[C[i]] = temp[1:]

def solve():
    global ans
    combs = []
    for i in range(N+1):
        combs.extend(combinations(C,i))

    # Total: O(2^N*N*M)
    for comb in combs:  #O(2^N)
        L = [0 for i in range(M)]
        cost = 0
        ok = True

        for k in comb:  #O(N)
            cost += k
            for i in range(M): #O(M)
                L[i] += D[k][i]
        print(comb, L, cost)
        for i in range(M):
            if L[i] < X: 
                ok = False
            
        if ok:
            ans = min(ans,cost)

    if ans == 12345678:
        print(-1)
    else:
        print(ans)
solve()


N, M , X = map(int, input().split())
C = [0 for i in range(N)]
A = [[]for i in range(N)]


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

def solve():
    ans = float('inf')
    # Total: O(2^N*N*M)
    total = 1 << N
    for mask in range(total):  #O(2^N)
        L = [0 for i in range(M)]
        cost = 0
        
        for i in range(N):  #O(N)
            if (mask >> i) & 1:
                cost += C[i]
                for j in range(M): #O(M)
                    L[j] += A[i][j]
            
        ok = True
        for i in range(M):
            if L[i] < X: 
                ok = False
        print(L, cost, ok)
        if ok:
            ans = min(ans,cost)

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


N, M , X = map(int, input().split())
C = [0 for i in range(N)]
A = [[]for i in range(N)]


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

def solve():
    ans = float('inf')
    # Total: O(2^N*N*M)
    total = 1 << N
    for mask in range(total):  #O(2^N)
        L = [0 for i in range(M)]
        cost = 0
        
        for i in range(N):  #O(N)
            if (mask >> i) & 1:
                cost += C[i]
                for j in range(M): #O(M)
                    L[j] += A[i][j]
            
        ok = True
        for i in range(M):
            if L[i] < X: 
                ok = False
        #print(L, cost, ok)
        if ok:
            ans = min(ans,cost)

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


Verdicts: Wrong Answer

Wrong Answer

Accepted