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 fractions import gcd
from functools import reduce
# from collections import deque
# from math import factorial
import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import itertools
# import statistics
# import numpy as np
# n = int(input())

# a = list(map(int, input().split()))

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

# n = int(input())
# n, m = list(map(int, input().split()))
a = []
for i in range(n):
    b = list(map(int, input().split()))
    t = sum(b)-b[0]
    # print(t)
    b.append(b[0]/t)
    a.append(b)

a_sorted = sorted(a, key=lambda x: x[-1])


money = 0
point = [0]*m
over = [0]*m
for i in range(n):
    fin = True
    money += a_sorted[i][0]
    for j in range(m):
        point[j] += a_sorted[i][j+1]
    for j in range(m):
        if point[j] < x:
            fin = False
        else:
            over[j] = point[j]-x
    if fin:
        k = []
        for i in range(n):
            kouho = True
            for j in range(m):
                if a_sorted[i][j+1] > over[j]:
                    kouho = False
            if kouho:
                k.append(i)
        k.sort(reverse=True)
        if len(k) != 0:
            for i in range(len(k)):
                for j in range(m):
                    point[j] -= a_sorted[i][j+1]
                    if point[j] < x:
                        print(money)
                        exit()
                money -= a_sorted[i][0]
        # print(over)
        for j in range(m):
            print(money)
            exit()
    # print(check)
print(-1)



from fractions import gcd
from functools import reduce
# from collections import deque
# from math import factorial
import collections
import math
import sys
sys.setrecursionlimit(2000000)
n, m, x = list(map(int, input().split()))
# a = list(map(int, input().split()))

#n = int(input())
# n, m = list(map(int, input().split()))
a = []
for i in range(n):
    b = list(map(int, input().split()))
    t = sum(b)-b[0]
    #print(t)
    b.append(b[0]/t)
    a.append(b)

a_sorted = sorted(a, key=lambda x: x[-1])

money = 0
point = [0]*m
for i in range(n):
    fin = True
    money += a_sorted[i][0]
    for j in range(m):
        #print(money)
        point[j] += a_sorted[i][j+1]
        
    #print(point, end=" ")
    #print(money)
    for j in range(m):
        if point[j] < x:
            fin = False
    if fin:
        print(money)
        exit()

    # print(check)
print(-1)



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

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


def calcPoint(point, n):
    for i in range(m):
        point[i] += a[n][i+1]
    return point


def judgePoint(point):
    for i in range(m):
        if point[i] < x:
            return False
    return True


ans = []
for i in range(2**n):  
    buy = []
    for j in range(n):  
        if((i >> j) & 1):  
            buy.append(1)
        else:
            buy.append(0)
    price = 0
    point = [0]*m
    for i in range(n):
        if buy[i] == 1:
            calcPoint(point, i)
            price += a[i][0]
    if judgePoint(point):
        ans.append(price)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))


Verdicts: Runtime Error

Runtime Error

Accepted