Problem:


Score : 300 points

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.

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

0\leq A_{i, j} \leq 10^5

Input

Input is given from Standard Input in the following format:

N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{N,M}

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.

Sample Input 1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

Sample Output 1

120

Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.

Sample Input 2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

Sample Output 2

-1

Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.

Sample Input 3

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Sample Output 3

1067



Sample input:
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Sample output:
120

Submission status: Accepted

Solution code:
import sys


try:
    sys.stdin = open(sys.path[0] + '\\input.txt', 'r')
    sys.stdout = open(sys.path[0] + '\\output.txt', 'w')
except FileNotFoundError:
    pass


n, m, x = list(map(int, input().split()))
arr = []
c = []

for i in range(n):
    row = list(map(int, input().split()))
    c.append(row[0])
    arr.append(row[1:])

mincost = float('inf')

for i in range(1 << n):
    temp = []
    cost = 0

    for j in range(n):
        if i & (1 << j):
            temp.append(j)
            cost += c[j]

    if temp:
        res = [0] * m
        for k in temp:
            for i in range(m):
                res[i] += arr[k][i]

        flag = True
        for i in res:
            if i < x:
                flag = False
                break

        if flag:
            mincost = min(mincost, cost)

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
books = []
for _ in range(N):
    line = list(map(int,input().split()))
    books.append(line)

values = []
for i in range(2**N):
    bags = []
    for j in range(N):
        if ((i >> j) & 1):
            bags.append(j)
    
    value = 0
    algs = [0] * M
    for k in bags:
        value += books[k][0]
        for l in range(M):
            algs[l] += books[k][l+1]
    
    for r in algs:
        if r < X:
            break
    else:
        values.append(value)
    
if len(values) == 0:
    print(-1)
else:
    print(min(values))

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for _ in range(n)]
a=[np.array(i[1:]) for i in ca]
c=[i[0] for i in ca]
xx=np.array([x]*m)
ans=pow(10,9)

for i in range(2**n):
  count=0
  aa=np.array([0]*m)
  for j in range(n):
    if ((i >> j) & 1):
      aa+=a[j]
      count+=c[j]  
    if all(i>=x for i in aa):
      ans=min(ans,count)
print(ans if ans<pow(10,9) else -1)

Submission status: Accepted

Solution code:
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
#x = int(input())
n, m, x = map(int, sys.stdin.readline().split())
#s = input()
#h = list(map(int, sys.stdin.readline().split()))

l = []
for i in range(n):
    l.append(list(map(int, sys.stdin.readline().split())))

ans = 10 ** 7

for j in range(2 ** n):
    bi = format(j, "b")
    if len(bi) != n:
        for k in range(n-len(bi)):
            bi = "0" + bi

    p = [0 for i in range(m+1)]
    for k in range(n):
        if bi[k] == "1":
            for i in range(m+1):
                p[i] += l[k][i]


    for i in range(m):
        if p[i+1] < x:
            break

        if i == m-1:
            if ans > p[0]:
                ans = p[0]

if ans == 10 ** 7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]

ans = float('inf')
for i in range(2**N):
    bit = str(bin(i))[2:].zfill(N)
    result = [0] * M
    cost = 0
    for j in range(N):
        if bit[j] == '1':
            C = CA[j][0]
            A = CA[j][1:]
            cost += C
            for k in range(M):
                result[k] += A[k]
    ok = True
    for j in range(M):
        if result[j] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
from itertools import combinations, chain

def main():
    n,m,x = map(int, input().split())
    books = [list(map(int, input().split())) for _ in range(n)]
    comb = [*chain(*(combinations(books, n+1) for n in range(len(books))))]
    m_list = []
    for c in comb:
        valid = True
        for i in range(1,m+1):
          if not valid:
            break
          s = sum([k[i] for k in c])
          if s < x:
            valid = False
            break
        if valid:
            m_list.append(sum([k[0] for k in c]))
    if len(m_list) == 0:
        print(-1)
    else:
        print(min(m_list))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import itertools

def main():

    input = stdin.readline

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

    for _ in range(N):
       C.append(list(map(int,input().split())))

    ans_num = -1

    buy_list = [0] * (M+1)

    for i in range(1,N+1):
        for j in itertools.combinations(C, i):
            # 全部足す
            for k in j:
                buy_list = [x + y for (x, y) in zip(buy_list, k)]
            
            # 判定
            judge_list =  buy_list[1:]

            for l in judge_list:
                if l < X:
                    break
            else:
                if(ans_num == -1):
                    ans_num = buy_list[0]
                else:
                    ans_num = min(ans_num,buy_list[0])
            
            buy_list = [0] * (M+1)


    print(ans_num)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, M, X = list(map(int, input().split()))
    C = []
    A = [[] for i in range(N)]
    for n in range(N):
        row = list(map(int, input().split()))
        C.append(row[0])
        for m in range(M):
            A[n].append(row[m+1])

    smallest = 10**9
    for i in range(2 ** 12):
        binary = bin(i)[2:]
        if len(binary) > N:
            break
        head = N - len(binary)
        pattern = list('0'*head + binary)

        M_satisfy = [0 for i in range(M)]
        for idx, p in enumerate(pattern):
            if p == '1':
                for m in range(M):
                    M_satisfy[m] += A[idx][m]
        flag = True
        for m in range(M):
            if M_satisfy[m] < X:
                flag = False
        if flag == True:
            tmp = sum([int(pattern[i]) * C[i] for i in range(len(pattern))])
            if tmp < smallest:
                smallest = tmp
    if smallest == 10**9:
        print(-1)
    else:
        print(smallest)

    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N, M, X = map(int, input().split())
A = np.zeros((N,M))
C = np.zeros(N)
loop = itertools.product(range(0, 2), repeat=N)
minE = 100000000000
for i in range(N):
    c, *a = map(int, input().split())
    C[i] = c
    A[i] = np.array(a)
for num in loop:
    l = np.array(num)
    if(np.sum(l) == 0):
        continue
    cost = np.dot(C, l)
    hemi = np.dot(l, A)
    if(np.all(hemi >= X)):
        if(minE > cost):
            minE = cost
if(minE == 100000000000):
    print("-1")
else:
    print(int(minE))

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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


zeroone = [0, 1]
zeroone_list = list(itertools.product(zeroone, repeat=N))

ans = float('inf')

for i in range(len(zeroone_list)):
    temp_l = [0]*(M+1)
    for j in range(N):
        if zeroone_list[i][j] == 1:
            temp_l = list(np.array(temp_l) + np.array(l[j]))

    if min(temp_l[1:M+1]) >= X:
        ans = min(ans, temp_l[0])

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

book=[]

mincost=10**12

for i in range(n):
    l=list(map(int,input().split()))
    book.append(l)

nl=np.array(book)

for i in range(2**n):
    bag=np.array([0]*(m+1))
    for j in range(n):
        if((i>>j)&1):
            bag+=nl[j]
    flag=True
    for j in range(1,m+1):
        if bag[j]<x:
            flag=False
    if flag and bag[0]<mincost:
        mincost=bag[0]

if mincost==10**12:
    mincost=-1
    
print(mincost)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[0]*N
a=[0]*N
for i in range(N):
  CA=list(map(int,input().split()))
  C[i]=CA[0]
  a[i]=CA[1:M+1]
cost_min = 100000000000000000000
def dfs(A):
    global cost_min
    # 終端条件 --- N 重ループまで回したら処理して打ち切り
    if len(A) == N:
        cost=sel(A)
        if cost<cost_min:
          cost_min=cost
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

#選択するかしないか
def sel(A):
  d=[0]*M
  cost=0
  for i in range(N):
    if A[i]==1:
      cost+=C[i]
      for j in range(M):
        d[j]+=a[i][j]
  if min(d)>=X:
    return cost
  return 100000000000000000000

dfs([])
if cost_min==100000000000000000000:
  print(-1)
else:print(cost_min)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


N,M,X = map(int,input().split())
table = []
ans = float("inf")


for i in range(N):
    s = list(map(int,input().split()))
    table.append(s)

for i in range(2**N):
    scores = [X]*M
    temp = 0
    for j in range(N):
        if (i>>j) & 1:
#            print(j)
            temp += table[j][0]
            for k in range(M):
                scores[k] -= table[j][k+1]
#    print(i,scores)
    if all(i <=0 for i in scores):
        ans = min(ans,temp)
print(ans if ans!=float("inf") else -1)

Submission status: Accepted

Solution code:
N ,M, X = map(int, input().split())
li = []
minkane = -1
for i in range(N):
    li.append(list(map(int, input().split())))
for i in range(2 ** N):
    kane = 0
    li2 = [0 for k in range(M)]
    for j in range(N):
        if i & (1 << j) != 0:
            kane += li[j][0]
            for l in range(len(li2)):
                li2[l] += li[j][l+1]
    flag = 1
    for j in range(len(li2)):
        if li2[j] < X:
            flag = 0
    if flag == 1:
        if minkane == -1:
            minkane = kane
        else:
            minkane = min(minkane, kane)
print(minkane)

Submission status: Accepted

Solution code:
from itertools import combinations
N,M,X = map(int,input().split())
C = []
for _ in range(N):
  C.append([int(v) for v in input().split()])
Ca,Aa = [],[]
for k in range(1,N+1):
  for v in combinations(C,k):
    tmp = [0]*(M+1)
    for v2 in v:
      for i,v3 in enumerate(v2):
        tmp[i]+=v3
    isOK = True
    for v2 in tmp[1:]:
      if v2 < X:
        isOK = False
        break
    if isOK:
      #print(tmp)
      Ca.append(tmp[0])
if len(Ca) == 0:
  print(-1)
else:
  print(min(Ca))

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
table = [tuple(map(int, input().split())) for _ in range(n)]
ans = []
for i in range(1,n+1):
    for cap in itertools.combinations(table, i):
        money = 0
        a = [0] * m
        for j in cap:
            money += j[0]
            for k in range(m):
                a[k] += j[k+1]
        if not len([l for l in a if l < x]):
            ans.append(money)
if not ans:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
def su(s, i):
    global n, g
    if i == n:
        g.append(s)
    else:
        su(s + '1', i+1)
        su(s + '0', i+1)


n, m, x = map(int, input().split())
a = [[] for i in range(n)]
c = [0] * n
for i in range(n):
    s = list(map(int, input().split()))
    c[i] = s[0]
    a[i]= list(s[1:])
cost = 10**7
g = []
su('', 0)
for i in g:
    s = [0]*m
    h = 0
    for j in range(n):
        if i[j] == '1':
            h += c[j]
            for k in range(m):
                s[k] += a[j][k]
    f = True
    for k in range(m):
        if s[k] < x:
            f = False
    if f:
        cost = min(cost, h)
if cost == 10**7:
    print("-1")
else:
    print(cost)

Submission status: Accepted

Solution code:

import itertools
import sys
n, m, x = map(int, input() .split())
ca = [list(map(int, input() .split())) for _ in range(n)]


max_acheive = [0 for _ in range(m)]
for i in range(n):
    for j in range(m):
        max_acheive[j] += ca[i][j+1]

for j in range(m):
    if max_acheive[j] < x:
        print(-1)
        sys.exit()

cost = []
all_flag = []
for i in range(1,n+1):
    options = list(itertools.combinations(range(n), i))
    for j,option in enumerate(options):
        acheive = [0 for _ in range(m)]
        cost.append(0)
        for k,book in enumerate(option):
            for ability in range(m):
                acheive[ability] += ca[book][ability+1]
            cost[-1] += ca[book][0]
        flag = 0
        for pp in range(m):
            if acheive[pp] >= x:
                flag+=1
        if flag != m:
            all_flag.append(0)
        else:
            all_flag.append(1)
min_cost = 10e+10
for i in range(len(cost)):
    if all_flag[i] == 1 and min_cost>cost[i]:
        min_cost = cost[i]
print(min_cost)

Submission status: Accepted

Solution code:
import itertools

n,m,x = map(int,input().split())
li = []
mn = 10**20
for i in range(n):
    buf = [int(x) for x in input().split()]
    li.append(buf)

for i in range(1,n+1):
    for v in itertools.combinations(li,i):
        sm = 0
        flag = False
        ans_li = [0] * m
        count = 0
        for j in range(len(v)):
            sm += v[j][0]
            tmp = v[j][1:len(v[j])]
            for k in range(len(tmp)):
                ans_li[k] += tmp[k]
        for l in range(m):
            if ans_li[l] >= x:
                count += 1
        if count == m:
            if sm < mn:
                mn = sm

if mn == 10**20:
    print(-1)
else:
    print(mn)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())

c = []
a = []
for _ in range(n):
   tmp = list(map(int, input().split()))
   c.append(tmp.pop(0))
   a.append(tmp)

ans = float('inf')
for i in range(2**n):
   cost = 0
   und = [0] * m
   for j in range(n):
      if ((i >> j) & 1):
         for k in range(m):
            und[k] += a[j][k]
         cost += c[j]

   if min(und) >= x:
      ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = [tuple(map(int, input().split())) for _ in range(N)]

from itertools import product

ans = -1
for bools in product((True, False), repeat=N):
  M_list = [0] * M
  t = 0
  for i in range(len(bools)):
    if bools[i]:
      for j in range(1, len(CA[i])):
        M_list[j-1] += CA[i][j]
      t += CA[i][0]
  for e in M_list:
    if e < X:
      break
  else:
    if ans < 0:
      ans = t
    else:
      ans = min(ans, t)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)

# 1 ✕ N
N, M, X = list(map(int, input().rstrip().split()))

# N ✕ M (2D array)
A = list(input().rstrip().split() for _ in range(N))

ans = 1e9
for bit in range(2 ** N):
    total = 0
    array = [0 for _ in range(M)]

    for i in range(N):
        if bit & 1 << i:
            total += int(A[i][0])
            for j in range(M):
                array[j] += int(A[i][j + 1])

    found = True
    for i in range(M):
        if array[i] < X:
            found = False

    if found:
        ans = min(ans, total)

print(-1 if ans == 1e9 else ans)

Submission status: Accepted

Solution code:
def sum_list(l1, l2):
  return [i+j for i, j in zip(l1, l2)]

def judge(l):
  for i in l[1:]:
    if i < X:
      return False
  return True

N, M, X = map(int, input().split())
array = []
zeros = [0]*(M+1)
for i in range(N):
  row = [j for j in map(int, input().split())]
  array.append(row)
  zeros = sum_list(zeros, row)

if not judge(zeros):
  print(-1)
  exit()

ret = float('inf')
for i in range(2**N):
  arr = [0]*(M+1)
  cost = 0
  for j in range(N):
    if i >> j & 1:
      arr = sum_list(arr, array[j])
  if judge(arr):
    ret = min(ret, arr[0])
    
print(ret)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m,x = map(int, input().split())
c = []
a = []
for i in range(n):
    t = list(map(int, input().strip().split()))
    c.append(t[0])
    a.append(t[1:])

a = np.array(a)

W = []
for i in range(1,n+1):
    Q = list(itertools.combinations(range(1, n + 1), i))
    for q in Q:
        W.append(list(q))

#print(W)
min = 1e10 + 9
flag = False
for w in W:
    z = np.zeros((m))
    ct = 0
    #print('---')
    #print(w)
    for i in range(len(w)):
        ct += c[w[i]-1]
        z += a[w[i]-1]
        #print(z)
        #print(ct)

    #print(len(np.where(z>=x)[0]),np.where(z>=x)[0])
    if len(np.where(z>=x)[0])>= m:
        #print('find')
        if ct < min:
            min = ct
            flag = True
            #print('min:',min)
    #print('---')
if flag:
    print(min)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

N,M,X=map(int,input().split())
CA=[]
for _ in range(N):
    CA.append(np.array(list(map(int,input().split()))))

select=[]

price_min=10**9
kaeru=0


for select in product(range(2),repeat=N):
    #print(select)
    noryoku=np.array([0]*(M+1))
    #print(noryoku)
    for i in range(N):
        if select[i]==1:
           # print("yes")
            noryoku+=CA[i]
    if (noryoku[1:]>=X).all():
        kaeru=1
        price_min=min(price_min,noryoku[0])

if kaeru:
    print(price_min)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations


class Manual():
    def __init__(self, price, content):
        self.price = price
        self.content = content


def main():
    n, m, x = [int(x) for x in input().split()]
    manuals = []
    for _ in range(n):
        price, *contents = [int(x) for x in input().split()]
        manuals.append((price, contents))  # (price, [a, a, a ...])

    should_pay = float('inf')
    for pick in range(1, n + 1):
        for comb in combinations(manuals, pick):
            understanding = [0] * m
            total_price = 0
            for a_manual in comb:
                total_price += a_manual[0]
                for i, value in enumerate(a_manual[1]):
                    understanding[i] += value

            if min(understanding) >= x:
                should_pay = min(should_pay, total_price)

    if should_pay == float('inf'):
        return -1
    else:
        return int(should_pay)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(N)]
ans = 100000000000
for i in range(1 << N):
    c = 0
    lis = [0 for _ in range(M)]
    for j in range(N):
        if (i >> j)& 1:
            c += C[j][0]
            lis = [x + y for (x, y) in zip(lis, C[j][1:])]
    if (min(lis) >= X):
        ans = min(ans, c)
if (ans == 100000000000):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np 
from itertools import combinations

n, m, x = [int(i) for i in input().split()]
A = np.array([[int(i) for i in input().split()]for j in range(n)])
cost = n*(10**5)
A_index_set = range(n)
satisfy_flag = False
for L in range(1, n+1):
    for subset in combinations(A_index_set, L):
        ans = np.array([0 for i in range(m+1)])
        for j in subset:
            ans += A[j,:]
        for sub_j in range(1, m+1): # check if everyone is more than x
            if  ans[sub_j] < x:
                break
        else:
            satisfy_flag = True
            cost = min(cost, ans[0])
if satisfy_flag:
    print(cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int,input().split())

c_li = [0]*n
a_li = [[] for i in range(n)]
for i in range(n):
    c_li[i],*a_li[i] = map(int,input().split())

m_li = [0]*m
ans=float('inf')
for i in range(1,n+1):
    for l in itertools.combinations([i for i in range(n)],i):
        cost = 0
        m_tmp = [0]*m
        for j in l:
            cost+=c_li[j]
            m_tmp = [a+b for a,b in zip(a_li[j],m_tmp)]
        #print(l,cost,m_tmp)
        if all(x<=m for m in m_tmp):
            if ans>cost:
                ans=cost
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools

N,M,X = map(int, input().split())

C = []
for c in range(N):
    C.append(list(map(int, input().split())))

ans = float('inf')
L = list(range(N))
for i in range(1, N+1):
    for comb in itertools.combinations(L, i):
        kingaku = 0
        TM = [0]*M
        for c in comb:
            kingaku += C[c][0]
            for i in range(1,M+1):
                TM[i-1] += C[c][i]
        isOk = True
        for m in TM:
            if m < X:
                isOk = False
                break

        if isOk:
            ans = min(ans, kingaku)

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

Submission status: Accepted

Solution code:
def main():
    N, M, X = map(int, input().split())
    C = [0 for _ in range(N)]
    A = [[0 for _ in range(M)] for _ in range(N)]

    books = []

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

    # understanding = [0 for _ in range(M)]
    # cost = 0
    #
    # for c, a in books:
    #     cost += c
    #     for i in range(len(a)):
    #         understanding[i] += a[i]
    #
    # if min(understanding) < X:
    #     print(-1)
    # else:
    #     for c, a in sorted(books, key=lambda x: x[0]):
    #         if all([understanding[i] - a[i] >= X for i in range(len(a))]):
    #             understanding = [understanding[i] - a[i] >= X for i in range(len(a))]
    #             cost -= c
    #
    #     print(cost)

    min_cost = float('inf')

    for i in range(2 ** N):
        cost = 0
        understanding = [0 for _ in range(M)]

        for j in range(N):
            if i & (2 ** j):
                cost += C[j]
                understanding = [understanding[k] + A[j][k] for k in range(M)]

        # print(i, cost, understanding)

        if all([understanding[k] >= X for k in range(M)]) and cost < min_cost:
            min_cost = cost

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for _ in range(N)]
def judge(books):
    study = [0]*M
    money = 0
    for i in range(N):
        if(books[i] == "1"):
            for j in range(M):
                study[j] += CA[i][j+1]
            money += CA[i][0]
    #print(study)
    for i in range(M):
        if(study[i] < X):
            return -1
    return money
ans = 10**10
for i in range(0,2**N):
    books =  str('{:0100b}'.format(i))[100-N:]
    #print(books)
    tmp = judge(books)
    if(tmp == -1):
        continue
    ans = min(tmp,ans)
if(ans == 10**10):
    print("-1")
else:
    print(ans)

Submission status: Accepted

Solution code:
pi = 3.1415926

############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n,m,x = invr()
nums = []
ans = [10**8]

for i in range(n):
    nums.append(inlt())
    
def cal(ins):
    aaa = [0 for i in range(m)]
    cost = 0
    for i in ins:
        cost += nums[i][0]
        
        for index,j in enumerate(nums[i][1:]):
            aaa[index] += j

    for i in range(m):
        if aaa[i] < x:
            return 10**8
    else:
        return cost
    
def printCombination(arr, n, r): 
      
    # A temporary array to  
    # store all combination 
    # one by one 
    data = [0]*r; 
  
    # Print all combination  
    # using temprary array 'data[]' 
    combinationUtil(arr, data, 0,  
                    n - 1, 0, r); 
  
# arr[] ---> Input Array 
# data[] ---> Temporary array to 
#         store current combination 
# start & end ---> Staring and Ending 
#             indexes in arr[] 
# index ---> Current index in data[] 
# r ---> Size of a combination  
# to be printed  
def combinationUtil(arr, data, start,  
                    end, index, r): 
                          
    # Current combination is ready  
    # to be printed, print it 
    if (index == r):
        ins = []
        for j in range(r): 
            ins.append(data[j])

        result = cal(ins)
        if result < ans[0]:
            ans[0] = result 
        return; 
  
    # replace index with all 
    # possible elements. The 
    # condition "end-i+1 >=  
    # r-index" makes sure that  
    # including one element at 
    # index will make a combination  
    # with remaining elements at  
    # remaining positions 
    i = start;  
    while(i <= end and end - i + 1 >= r - index): 
        data[index] = arr[i]; 
        combinationUtil(arr, data, i + 1,  
                        end, index + 1, r); 
        i += 1; 
    
arr = [i for i in range(n)]
for i in range(1,n + 1):
    printCombination(arr,n,i)

print(ans[0] if ans[0] < 10**8 else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
C = []
for i in range(n):
    C.append(list(map(int, input().split())))

ans = []
import itertools
for tuple_ in itertools.product(range(2), repeat=n):
    res = [0]*(m+1)
    #print(tuple_)
    for i,f in enumerate(tuple_):
        if f:
            for j in range(m+1):
                res[j] += C[i][j]
    #print('res', res)
    ng = 0
    for k in range(m):
        if res[k+1] < x:
            ng += 1
    if ng == 0:
        ans.append(res[0])
if ans:
    print(min(ans))
else:
    print('-1')
#print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]

cost=99999999999999

for i in range(2**n):
    shujukudo=[0]*m
    tmp_cost=0
    for j in range(n):
        if ((i>>j)&1):
            for m_i in range(m):
                shujukudo[m_i]+=ca[j][m_i+1]
            tmp_cost+=ca[j][0]
    tf=[s >= x for s in shujukudo]
    if all(tf):
        cost=min(cost,tmp_cost)
print(cost if cost!=99999999999999 else -1)

Submission status: Accepted

Solution code:
import itertools

def main():
    N,M,X = list(map(int, input().split(' ')))
    
    inputs = []
    for _ in range(N):
        inputs.append(list(map(int, input().split(' '))))
        
    Ci = [s[0] for s in inputs]
    Aij = [s[1:] for s in inputs]
    
    # print(Ci, Aij)
    
    indexs = [i for i in range(N)]
    
    com = []
    for n in range(1,N+1):
        com.extend(list(itertools.combinations(
        indexs, n)))
    
    
    minimum = 100000000
    isOK = False
    for inds in com:
        # A,B,C=0,0,0
        # skills = [m for m in range(M)]
        skills = [0 for m in range(M)]
        MONE = 0
        for ind in inds: # (0,1)
            power = Aij[ind]
            skills = [power[i] + skills[i] for i in range(M)]
            MONE += Ci[ind]
        
        skills = [n >= X for n in skills]
        # print(skills, inds, MONE)
        if False not in skills:
            isOK = True
            minimum = min(minimum, MONE)
    
    if isOK is True:
        print(minimum)
    else:
        print('-1')
    
    
            
    

main()

Submission status: Accepted

Solution code:
import itertools
from operator import add

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

l = []

for _ in range(n):
    l.append(list(map(int,input().split())))

min_cost = -1

can = False

for buy_or_not in itertools.product(range(2), repeat=n):
    cost = 0
    m_list = [0] * m
    
    for i, j in enumerate(buy_or_not):
        if j:
            cost += l[i][0]
            m_list = list(map(add, m_list, l[i][1:]))

    m_check = [True if temp_m >= x else False for temp_m in m_list]

    if all(m_check):
        if min_cost == -1:
            min_cost = cost
        elif cost <= min_cost:
            min_cost = cost
    
print(min_cost)

Submission status: Accepted

Solution code:
# C
N, M, X = map(int, input().split())
ans = -1
lst = [list(map(int, input().split())) for i in range(N)]
ans = 10**9
for i in range(2 ** N):
    bag = []
    total = 0
    score = [0] * M
    for j in range(N):  
        if ((i >> j) & 1):  
            bag.append(lst[j])
    for k in bag:
        total += k[0]
        for idx, l in enumerate(k[1:]):
            score[idx] += l
    right_score = [m for m in score if m >= X]
    if (len(right_score) == M):
        ans = min(ans, total)
if (ans == 10**9):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [0] * n
a = []
for i in range(n):
    A = list(map(int, input().split()))
    c[i] = A[0]
    a.append(A[1:])

cmin = 100000 * n + 1

for bit in range(1 << n):
    A = [0] * m
    csum = 0
    for i in range(n):
        if bit & (1 << i):
            for j in range(m):
                A[j] += a[i][j]
            csum += c[i]

    f = True
    for i in A:
        if i < x:
            f = False

    if f:
        cmin = min(cmin, csum)

print((cmin if cmin != 100000 * n + 1 else -1))

Submission status: Accepted

Solution code:
def is_over(L):
    for l in L:
        if l < X:
            return False
    return True


def dfs(i, c, A):
    if i == N:
        if is_over(A):
            global min_c
            min_c = min(min_c, c)
    else:
        dfs(i+1, c, A)
        next = [A[k]+B[i][1][k] for k in range(M)]
        dfs(i+1, c+B[i][0], next)


N, M, X = map(int, input().split())
B = []
S = [[0]*(M) for _ in range(N+1)]
for i in range(1, N+1):
    ipt = list(map(int, input().split()))
    A = ipt[1:]
    B.append((ipt[0], A))
    for j in range(M):
        S[i][j] = S[i-1][j] + A[j]
min_c = 10**10
if is_over(S[-1]):
    dfs(0, 0, [0]*M)
    print(min_c)
else:
    print(-1)