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):
# coding: utf-8
# Your code here!
import itertools
import sys
N, M, X  = map(int, input().split())
money = []
A = []
ans = 0
for _ in range(N):
    nums = [int(x.strip()) for x in input().split(' ') ]
    money.append(nums[0])
    nums.pop(0)
    A.append(nums)
    
def run(lis, num, A, X, M):
    tmp_ans = sum(lis)
    for team in itertools.combinations(lis, num):
        count = 0
        for i in range(M):
            tmp = 0
            for j in list(team):
                tmp += A[lis.index(j)][i]
            if tmp >= X:
                count += 1
        if sum(list(team)) < tmp_ans and count == num:
            tmp_ans = sum(list(team))
    if not tmp_ans == sum(lis):
        print(tmp_ans)
        sys.exit()
for i in range(2, N+1):
    run(money, i, A, X, M)

print(-1)

# coding: utf-8
# Your code here!
import itertools
import sys
import copy
N, M, X  = map(int, input().split())
money = []
A = []
ans = 0
for _ in range(N):
    nums = [int(x.strip()) for x in input().split(' ') ]
    money.append(nums[0])
    nums.pop(0)
    A.append(nums)
    
def run(lis, num, A, X, M):
    ans_list = []
    for team in itertools.combinations(lis, num):
        count = 0
        for i in range(M):
            tmp = 0
            for j in list(team):
                tmp += A[lis.index(j)][i]
            if tmp >= X:
                count += 1
        if count == M:
            ans_list.append(sum(list(team)))
    if not len(ans_list) == 0:
        print(min(ans_list))
        sys.exit()
for i in range(1, N+1):
    run(money, i, A, X, M)
    print(i)

print(-1)

# coding: utf-8
# Your code here!
import itertools
import sys

N, M, X  = map(int, input().split())
money = []
A = []
ans = []
for _ in range(N):
    nums = [int(x.strip()) for x in input().split(' ') ]
    money.append(nums[0])
    nums.pop(0)
    A.append(nums)
num_money = []
for index, num in enumerate(money):
    num_money.append(index)
    
def run(lis, num, A, X, M, ans, money):
    ans_list = []
    for team in itertools.combinations(lis, num):
        count = 0
        for i in range(M):
            tmp = 0
            for j in list(team):
                tmp += A[j][i]
            if tmp >= X:
                count += 1
        if count == M:
            tmp_ans = []
            for n in list(team):
                tmp_ans.append(money[n])
            ans_list.append(sum(tmp_ans))
    if not len(ans_list) == 0:
        ans.append(min(ans_list))
    
    return ans
        
for i in range(1, N+1):
    ans = run(num_money, i, A, X, M, ans, money)
    
if not len(ans) == 0:
    print(min(ans))
    
else:
    print(-1)

Verdicts: Wrong Answer

Wrong Answer

Accepted