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):
n, m, x = map(int, input().split())
A = [[] for _ in range(n)]
cost = [0] * n
for i in range(n):
  c_as = list(map(int, input().split()))
  cost[i], A[i] = c_as[0], c_as[1:]
INF = 10**9
ans = INF
for s in range(0, 1 << n):
  smart = [0] * m
  cost_sum = 0
  for i in range(n):
    if (s >> i) % 2 == 0:
      continue
    cost_sum += c[i]
    for j in range(m):
      smart[j] += A[i][j]
  ok = True
  for j in range(m):
    if smart[j] < x:
      ok = False
  if ok:
    ans = min(ans, cost_sum)
if ans == INF:
  ans = -1
print(ans)
    

n, m, x = map(int, input().split())
l = []
dp = [[] for _ in range(n+1)]
for _ in range(n):
  a = list(map(int, input().split()))
  l.append(a)
dp[0].append([0 for _ in range(m+1)])
ans = []
for i in range(n):
  for row in dp[i]:
    dp[i+1].append(row)
    for j in range(m+1):
      row[j] += l[i][j]
    dp[i+1].append(row)
for row in dp[n]:
  cnt = 0
  for j in range(1, m+1):
    if row[j] >= x:
      cnt += 1
  if cnt == m:
    ans.append(row[0])
if len(ans) == 0:
  print(-1)
else:
  ans.sort()
  print(ans[0])

n, m, x = map(int, input().split())
l = []
dp = [[] for _ in range(n)]
for _ in range(n):
  a = list(map(int, input().split()))
  l.append(a)
dp[0].append([0] * (m+1))
ans = []
for i in range(n):
  for row in dp[i]:
    dp[i+1].append(row)
    cnt = 0
    for j in range(m+1):
      if j == 0:
        row[0] += l[i][0]
      else:
        row[j] += l[i][j]
        if row[j] >= x:
          cnt += 1
    if cnt == m:
      ans.append(row[0])
    dp[i+1].append(row)
if len(ans) == 0:
  print(-1)
else:
  ans.sort()
  print(ans[0])

n, m, x = map(int, input().split())
l = []
dp = [[] for _ in range(n+1)]
for _ in range(n):
  a = list(map(int, input().split()))
  l.append(a)
dp[0].append([0 for _ in range(m+1)])
ans = []
for i in range(n):
  for row in dp[i]:
    dp[i+1].append(row)
    cnt = 0
    for j in range(m+1):
      if j == 0:
        row[0] += l[i][0]
      else:
        row[j] += l[i][j]
        if row[j] >= x:
          cnt += 1
    if cnt == m:
      ans.append(row[0])
    dp[i+1].append(row)
if len(ans) == 0:
  print(-1)
else:
  ans.sort()
  print(ans[0])


n, m, x = map(int, input().split())
A = [[] for _ in range(n)]
cost = [0] * n
for i in range(n):
  c_as = list(map(int, input().split()))
  cost[i], A[i] = c_as[0], c_as[1:]
INF = 10**9
ans = INF
for s in range(0, 1 << n):
  smart = [0] * m
  cost_sum = 0
  for i in range(n):
    if (s >> i) % 2 == 0:
      continue
    cost_sum += cost[i]
    for j in range(m):
      smart[j] += A[i][j]
  ok = True
  for j in range(m):
    if smart[j] < x:
      ok = False
  if ok:
    ans = min(ans, cost_sum)
if ans == INF:
  ans = -1
print(ans)
    


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Accepted