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):
import sys
input = sys.stdin.readline
import itertools

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

ans = 999999
for i in range(1, N+1):
    for pair in itertools.combinations(values_list, i):
        this_m_dict = {}
        this_cost = 0
        for item in pair:
            for j in range(1, M+1):
                this_m_dict[j] = this_m_dict.get(j, 0) + item[j]
            this_cost += item[0]
        for myvalue in this_m_dict.values():
            if myvalue < X:
                break
        ans = min(this_cost, ans)

print(ans)

import sys
input = sys.stdin.readline
import itertools

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


for i in range(1, N+1):
    for pair in itertools.combinations(values_list, i):
        this_m_dict = {}
        this_cost = 0
        for item in pair:
            for j in range(1, M+1):
                this_m_dict[j] = this_m_dict.get(j, 0) + item[j]
            this_cost += item[0]
        for myvalue in this_m_dict.values():
            if myvalue < X:
                break
        ans = min(this_cost, ans)

print(ans)

import sys
input = sys.stdin.readline
import itertools


# N, M, X = map(int, input().split())
# values_list = []

#     values = list(map(int, input().split()))
#     values_list.append(values)

# ans = 0

#     for pair in itertools.combinations(values_list, i):
#         this_m_dict = {}
#         this_cost = 0
#         for item in pair:
#             for j in range(1, M+1):
#                 this_m_dict[j] = this_m_dict.get(j, 0) + item[j]
#             this_cost += item[0]
#         for myvalue in this_m_dict.values():
#             if myvalue < X:
#                 break
#         ans = min(this_cost, ans)

N, M, X = map(int, input().split())
A = []
C = []

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

INF = float('INF')
min_cost = INF

def dfs(i, cost, learn):
    if i == N:
        if min(learn) >= X: 
            return cost
        else:
            return INF

    else:
        new_learn = [(x+y) for (x, y) in zip(A[i], learn)]
        cost = min(dfs(i+1, cost, learn), dfs(i+1, cost + C[i], new_learn))
        return cost

min_cost = dfs(0, 0, [0] * M)

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

Verdicts: Wrong Answer

Runtime Error

Accepted