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 itertools
import numpy as np

n, m, x = map(int, input().split())
l = np.array([list(map(int, input().split())) for _ in range(n)])
num = [i for i in range(n)]

ans = 10**10
for i in range(1, n+1):
  for v in itertools.combinations(num, i):
    tmp = 0
    rikaido = np.array([0 for _ in range(m)])
    
    for each in v:
      tmp += l[each][0]
      rikaido += l[each][1:]
    
    if np.min(rikaido) >= x:
      ans = min(ans, tmp)
      
if ans == 10**10:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

best = float("inf")
for i in range(1<<n):
    sk = [0] * m
    pr = 0
    for j in range(n):
        if i&(1<<j):
            for k in range(m):
                sk[k] += arr[j][k+1]
            pr += arr[j][0]

    gud = True
    for e in sk:
        if e < x:
            gud = False
            break

    if gud:
        best = min(best, pr)

if best == float("inf"):
    best = -1
print(best)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[0]*N
A=[]
for i in range(N):
  x=list(map(int,input().split()))
  C[i]=x[0]
  A.append(x[1:])
ans=sum(C)+1
for i in range(2**N):
  summ=0
  x=[0]*M
  flag=True
  for j in range(N):
    if(i>>j & 1):
      for k in range(M):
        x[k]+=A[j][k]
      summ+=C[j]
  for k in range(M):
    if(x[k]<X):
      flag=False
  if(flag==True):
    ans=min(ans,summ)
if(ans<=sum(C)):
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)


def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


N,M,X=acinput()

books=[]
for i in range(N):
    books.append(acinput())
    

res=10**9
for k in range(2**N):
    bk=list(map(int,list(bin(k)[2:].zfill(N))))
    
    sm=0
    usd=np.array([0]*M)
    for l,s in enumerate(bk):
        if s==1:
            sm+=books[l][0]
            usd+=books[l][1:]
    
    #print(bk)
    #print(usd)
    if np.all(usd>=X):
        res=min(res,sm)
        
    
if res==10**9:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import sys
N,M,X=map(int, input().split())

i=0
lst = []
while i < N:
    m = map(int, input().split())
    lst.append(list(m))
    i+=1
arr = np.array(lst)

#Xに至らなかったとき
if np.min(np.sum(arr[:,1:], axis=0)) < X:
    print(-1)
    sys.exit()
data = arr[:,1:]
res = []
for i in range(1,N+1):
    for conbi in itertools.combinations(lst, i):
        arrx = np.array(conbi)
        if np.min(np.sum(arrx[:,1:], axis=0)) >= X:
            res.append(np.sum(arrx[:,0]))

print(min(res))

Submission status: Accepted

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

score = -1
for i in range(2**n):
    score_ = 0
    a = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                a[k] += v[j][k+1]
            score_ += v[j][0]
    if min(a) >= x:
        if score == -1:
            score = score_
        else:
            score = min(score_,score)
if score == -1:
    print(-1)
else:
    print(score)

Submission status: Accepted

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

ar = [[0]*(m+1)]*n

for i in range(n):
    ar[i] = [int(s) for s in input().split()]


#print(ar)

smp = 111

def goukei(bitt):
    bitt = str(bitt)
    cnt = 0
    mn = 0
    skl = [0]*m
    for i in bitt:
        if(i == "1"):
            mn += ar[cnt][0]
            skl = [x + y for (x, y) in zip(skl, ar[cnt][1:])]
            #skl += ar[cnt][1:]
        cnt += 1
    
    #print(bitt,mn,skl)    
    flag = 1
    if any(ss < x for ss in skl):
        flag = 0
    
    
    return mn,flag


#print(goukei(smp))
            

mx = 2**n 


mnmn = []

for i in range(mx+1):
    bit_sentaku = str(bin(i))
    bit_sentaku = bit_sentaku[2:]
    bit_sentaku = bit_sentaku.zfill(n)
    #print(goukei(bit_sentaku))
    if(goukei(bit_sentaku)[1] == 1):
        mnmn.append(goukei(bit_sentaku)[0])

if not(len(mnmn) == 0):
    print(min(mnmn))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for _ in range(n)]
ans=[-1]*(m+1)
tmp=[0]*(m+1)
for i in range(2**n):
  for j in range(n):
    if (i>>j)&1:
      for k in range(m+1):
        tmp[k]+=ca[j][k]
  for j in range(1,m+1):
    if tmp[j]<x:
      break
  else:
    if ans[0]>tmp[0] or ans[0]<0:
      ans=tmp
  tmp=[0]*(m+1)
print(ans[0])

Submission status: Accepted

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

costs = []
a = []
ans = 10 ** 9

for i in range(n):
    c, *j = map(int, input().split())
    costs.append(c)
    a.append(j)

for y in range(2 ** n):
    total = 0
    b = [0] * m
    bi = '{:b}'.format(y).zfill(n)
    for i in range(n):
        if bi[i] == '1':
            total += costs[i]
            r = a[i]
            for j in range(m):
                b[j] += r[j]
    if all([k >= x for k in b]):
        ans = min(ans, total)

if ans == 10 ** 9:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
X=int(a[2])
list1=[]
for i in range(N) :
  k=input().split()
  k=[int(j) for j in k]
  list1.append(k)

flag1=True
def count(item,i) :
  count1=0
  for a in item :
    count1+=a[i]
  return count1

def algo(item,i) :

  for j in range(1,i+1) :
    if count(item,j)<X :
      return False
  return True


import itertools
value_list=[]
for i in range(1,N+1) :
  c=list(itertools.combinations(list1,i))


  for item in c :
    item1=list(item)


    if algo(item1,M) :
      value_list.append(count(item1,0))

if value_list!=[] :
  print(min(value_list))
else :
  print('-1')

Submission status: Accepted

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

cost_list = []
for choice in range(n+1):
  for v in itertools.combinations(ca, choice):
    cost = 0
    us = [0] * m
    for t in v:
      cost += t[0]
      for i in range(m):
        us[i] += t[i+1]
    flag = True
    for check in range(m):
      if us[check] < x:
        flag = False
    if flag == True:
      cost_list.append(cost)

if len(cost_list) == 0:
  print(-1)
else:
  print(min(cost_list))

Submission status: Accepted

Solution code:
def solve():
    N, M, X = map(int, input().split())
    AC = []
    ans = 10**8
    for n in range(N):
        AC.append(list(map(int, input().split())))
    for i in range(2**N):
        level = [0]*M
        cost = 0
        for j in range(N):
            if ((i >> j) & 1):
                for l in range(M):
                    level[l] += AC[j][l+1]
                cost += AC[j][0]
        if (min(level) >= X) and (ans > cost):
            ans = cost
    if ans == 10**8:
        print(-1)
    else:
        print(ans)


solve()

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int,input().split())
boollist = list(map(list,itertools.product([True,False],repeat = n)))
itemlist = []
for i in range(n):
    itemlist.append(list(map(int,input().split())))

a = 10**8
for i in range(len(boollist)):
    unders = [0 for i in range(m)]
    money = 0
    for j in range(n):
        if boollist[i][j]:
            money += itemlist[j][0]
            for k in range(m):
                unders[k] += itemlist[j][k+1]
    if min(unders) >= x and money < a:
        a = money
if a == 10**8:
    print(-1)
else:
    print(a)

Submission status: Accepted

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

from itertools import combinations

combs = list()
for k in range(1, n+1):
    combs.extend(list(combinations(range(0, n), k)))

mn = -1
for comb in combs:
    money = 0
    us = [0] * m
    for i in list(comb):
        b = bs[i]
        money += b[0]
        for j, u in enumerate(b[1:]):
            us[j] += u

    is_ok = True
    for i in range(m):
        if us[i] < x:
            is_ok = False
            break
    if is_ok:
        if mn < 0 or money < mn:
            mn = money

print(mn)

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())
c = [0] * n
a = np.zeros((n, m))
for i in range(n):
    t = [int(j) for j in input().split()]
    c[i] = t[0]
    a[i] = t[1:]
low = float('inf')
for i in range(2 ** n):
    price = 0
    score = np.zeros(m)
    for j in range(n):
        if i & (1 << j):
            score += a[j]
            price += c[j]
    if len(score[score >= x]) == m:
        low = min(low, price)
print(-1) if low==float('inf') else print(low)

Submission status: Accepted

Solution code:
def main():
    import sys
    import numpy as np
    import itertools
    N,M,X=list(map(int,sys.stdin.readline().split()))
    C=[]
    for i in range(N):
        C.append(list(map(int,sys.stdin.readline().split())))

    C=np.array(C)
    costs=C[:,0]
    C=C[:,1:]
    cost=10**12
    for a in list(itertools.product([0,1], repeat=N)):
        if all((np.sum(C.T*np.array(a),axis=1)>=X).tolist()):
            cost=min(cost,np.sum(costs*np.array(a)))
    if cost==10**12:
        print(-1)
    else:
        print(cost)
        


main()

Submission status: Accepted

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

mincost = 10**9
for i in range(2**n):
	cost = 0
	knowledge = [0]*m
	for j in range(n):
		if i%2 == 1:
			cost += books[j][0]
			for b in range(m):
				knowledge[b] += books[j][b+1]
		i = i >> 1
	if min(knowledge) >= x and cost < mincost:
		mincost = cost

if mincost == 10**9:
	print(-1)
else:
	print(mincost)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
pattern = []
for i in range(2**(n)):
    tmp = [0 for i in range(n)]
    for j in range(n):
        if i>>j & 1:
            tmp[j] = 1
    pattern.append(tmp)

ans = 10**9
Input= []
for i in range(n):
    tmp = [int(i) for i in input().split()]
    Input.append(tmp)
for i in pattern:
    score = [0 for j in range(m)]
    tmp_ans = 0
    Flag = True
    for j in range(len(i)):
        if i[j]==0:
            continue
        else:
            tmp_ans += Input[j][0]
            for k in range(m):
                score[k] += Input[j][k+1]
    for k in range(m):
        if score[k]<x:
            Flag = False
    if Flag == False:
        continue
    ans = min(ans,tmp_ans)
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

bit=[]
for i in range(2**n):
    b=[]
    for j in range(n):
        if (i>>j & 1):
            b.append(1)
        else:
            b.append(0)
    bit.append(b)

ans_list=[]
#bitの各要素
for i in range(len(bit)):
    a=[0 for l in range(m+1)]
    for j in range(n):
        if bit[i][j]==1:
            for k in range(m+1):
                a[k]=a[k]+book[j][k]
    if min(a[1:])>=x:
        ans_list.append(a[0])
    a=[]
    
if len(ans_list)==0:
    print(-1)
else:
    print(min(ans_list))

Submission status: Accepted

Solution code:
#C
from itertools import combinations

N,M,X=map(int,input().split())
Z=[[int(x) for x in input().split()] for i in range(N)]
num=[i for i in range(N)]

com=[]
for i in range(1,N+1):
    com=com+list(combinations(num, i))
    
Min=10**8
for A in com:
    cost=0
    B=[0 for j in range(M)]
    for i in A:
        cost+=Z[i][0]
        for j in range(M):
            B[j]+=Z[i][j+1]
        
    if min(B)<X:
        continue
    else:
        Min=min(Min,cost)
        
if Min==10**8:
    print(-1)
else:
    print(Min)

Submission status: Accepted

Solution code:
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
def printCombination(arr, n, r): 
	data = [0] * r 
	combinationUtil(arr, n, r, 0, data, 0) 
def combinationUtil(arr, n, r, index, data, i): 
	if (index == r): 
		ans=[]
		for j in range(r): 
			ans.append(data[j]) 
		f.append(ans)
		return
	if (i >= n): 
		return
	data[index] = arr[i] 
	combinationUtil(arr, n, r, index + 1, 
					data, i + 1) 
	combinationUtil(arr, n, r, index, 
					data, i + 1) 


n,m,x=map(int,input().split())
cost=[]
l=[]
for i in range(n):
	l.append(list(map(int,input().split())))
z=[i for i in range(n)]
for i in range(1,n+1):
	f=[]
	printCombination(z,n,i)
	for t in f:
		ans=0
		ansd=[0 for i in range(m)]
		for j in t:
			ans+=l[j][0]
			for k in range(m):
				ansd[k]+=l[j][k+1]
		flag=1
		for k in ansd:
			if k<x:
				flag=0
		if flag==1:
			cost.append(ans)
if len(cost)>0:
	print(min(cost))
else:
	print(-1)

Submission status: Accepted

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

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

y = 0
for i in range(2 ** n):
  lb = [0]*(m+1)
  for j in range(n):
    if ((i >> j) & 1):
      lb = [x + y for (x, y) in zip(lb, la[j][:])] 
  frg=1
  for h in range(m):
    if lb[h+1]<x:
      frg=0
  if frg==1:
    if lb[0] <= y or y==0:
      y=lb[0]
  del lb[:]
print(y if y>0 else -1)

Submission status: Accepted

Solution code:
import itertools
N,M,X=map(int,input().split())
ans=13*10**5
List=[]
for _ in range(N):
  List.append([int(i) for i in input().split()])
for i in range(0,N):
  for j in itertools.combinations(range(N),i+1):
    tmp=[0]*(M+1)
    for k in j:      
      for l in range(M+1):
        tmp[l]+=List[k][l]
    if len([m for m in tmp[1:] if m>=X])==M:
      ans=min(ans,tmp[0])
if ans==13*10**5:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
n, m, x = [int(elem) for elem in input().split()]

cs = []
a_lsts = []
for i in range(n):
    elems = [int(elem) for elem in input().split()]
    c, a_lst = elems[0], elems[1:]
    cs.append(c)
    a_lsts.append(a_lst)


min_ = -1
for i in range(2 ** n):
    s = '0' * n + bin(i)[2:]
    s = s[-n:]
    res = 0
    costs = [0] * m
    for j in range(n):
        if s[j] == '0':
            pass
        else:
            res += cs[j]
            costs = [costs[k] + a_lsts[j][k] for k in range(m)]
    if all(elem >= x for elem in costs):
        if min_ == -1:
            min_ = res
        elif min_ > res:
            min_ = res
print(min_)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
ans = -1

N, M, X = map(int, input().split())
A = np.ndarray(shape=(N, M), dtype=int)
C = np.ndarray(shape=(N, ), dtype=int)
ans = []
costs = []
money = []
for i in range(N):
    inp = list(map(int, input().split()))
    C[i] = inp[0]
    A[i] = inp[1:]
for r in range(N):
    for c in combinations(range(N), r + 1):
        if min(np.sum(A[list(c)], axis=0)) >= X:
            costs.append(np.sum(C[list(c)]))
if len(costs) == 0:
    print(-1)
else:
    print(min(costs))

Submission status: Accepted

Solution code:
inputLine=input()
N=int(inputLine.split(" ")[0])
M=int(inputLine.split(" ")[1])
X=int(inputLine.split(" ")[2])

CandA=[]
for i in range(N):
    inputLine=input()
    CandA.append(inputLine.split(" "))

for i in range(len(CandA)):
    for j in range(len(CandA[i])):
        CandA[i][j] = int(CandA[i][j])

algorithmLevel = []
for i in range(M):
    algorithmLevel.append(0)

result = -1

for a1 in range(2):    
    for a2 in range(2):
        for a3 in range(2):
            for a4 in range(2):
                for a5 in range(2):
                    for a6 in range(2):
                        for a7 in range(2):
                            for a8 in range(2):
                                for a9 in range(2):
                                    for a10 in range(2):
                                        for a11 in range(2):
                                            for a12 in range(2):
                                                
                                                for i in range(M):
                                                    algorithmLevel[i] = 0

                                                for i in range(1, N+1):
                                                    for j in range(1, M+1):
                                                        if i == 1:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a1

                                                        if i == 2:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a2

                                                        if i == 3:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a3

                                                        if i == 4:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a4

                                                        if i == 5:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a5

                                                        if i == 6:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a6

                                                        if i == 7:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a7

                                                        if i == 8:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a8

                                                        if i == 9:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a9

                                                        if i == 10:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a10

                                                        if i == 11:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a11

                                                        if i == 12:
                                                            algorithmLevel[j-1] += CandA[i-1][j] * a12
                                                
                                                levelCheck = True
                                                for i in range(len(algorithmLevel)):
                                                    if algorithmLevel[i] < X:
                                                        levelCheck = False
                                                if levelCheck == True:
                                                    sumBooksPrice = 0
                                                    for i in range(1, N+1):
                                                        if i == 1:
                                                            sumBooksPrice += CandA[i-1][0] * a1

                                                        if i == 2:
                                                            sumBooksPrice += CandA[i-1][0] * a2

                                                        if i == 3:
                                                           sumBooksPrice += CandA[i-1][0] * a3

                                                        if i == 4:
                                                           sumBooksPrice += CandA[i-1][0] * a4

                                                        if i == 5:
                                                           sumBooksPrice += CandA[i-1][0] * a5

                                                        if i == 6:
                                                           sumBooksPrice += CandA[i-1][0] * a6

                                                        if i == 7:
                                                           sumBooksPrice += CandA[i-1][0] * a7

                                                        if i == 8:
                                                           sumBooksPrice += CandA[i-1][0] * a8

                                                        if i == 9:
                                                           sumBooksPrice += CandA[i-1][0] * a9

                                                        if i == 10:
                                                           sumBooksPrice += CandA[i-1][0] * a10

                                                        if i == 11:
                                                           sumBooksPrice += CandA[i-1][0] * a11

                                                        if i == 12:
                                                           sumBooksPrice += CandA[i-1][0] * a12

                                                    if result == -1:
                                                        result = sumBooksPrice                                                        
                                                    else:
                                                        if result > sumBooksPrice:
                                                            result = sumBooksPrice

print(result)

Submission status: Accepted

Solution code:
s = input().split()

N = int(s[0])
M = int(s[1])
X = int(s[2])

C = []
A = []

for i in range(N):
  t = input().split()
  C.append(int(t[0]))
  A_each = []
  for j in range(M):
    A_each.append(int(t[j+1]))
  A.append(A_each)
  
mini = -1
  
for i in range(2 ** N):
  bina = bin(i)[2:]
  money = 0
  result = []
  for x in range(M):
  	result.append(0)
  while(len(bina) < N):
    bina = "0" + bina
  for k in range(N):
    if bina[k] == "1":
      money += C[k]
      for j in range(M):
        result[j] += A[k][j]
  test = 0
  #print(str(result), str(money))
  for n in range(M):
    if result[n] >= X:
    	test += 1
  if test == M:
    if money < mini or mini == -1:
      mini = money
      
print(mini)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n,m,x = map(int,input().split())
c = [0] * n
a = [0] * n
for i in range(n):
    p = list(map(int,input().split()))
    c[i] = p[0]
    a[i] = list(p[1:])
p_min = float('inf')

for i in range(n):
    for it in itertools.combinations(a,i+1):
        ans = [0] * m
        for li in it:
            ans += np.array(li)
        if all([item >= x for item in ans]):
            p_ans = 0
            for ind in it:
                p_ans += c[a.index(ind)]
            p_min = min(p_min,p_ans)
if p_min == float('inf'):
    print(-1)
else:
    print(p_min)

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
ca = []
for _ in range(n): ca.append(list(map(int, input().split())))
ans = 10 ** 19
t = False
for i in range(1, n+1):
    for idx in itertools.combinations(range(n), i):
        l = [0]*m
        c = 0
        for j in idx:
            for k, v in enumerate(ca[j][1:]):
                l[k] += v
            c += ca[j][0]
        if min(l) >= x:
            ans = min(ans, c)
            t = True
if t: print(ans)
else: print(-1)

Submission status: Accepted

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

stk = [[0 for _ in range(m + 1)]]
for i in range(n):
    cost = books[i][0]
    effect = books[i][1:]
    for j in range(len(stk)):
        sc = stk[j][0]
        tmp = []
        for k in range(m):
            tmp.append(effect[k] + stk[j][k + 1])
        stk.append([sc + cost] + tmp)

stk.sort()

for s in stk:
    cost = s[0]
    eff = s[1:]
    is_ok = True
    for e in eff:
        if e < x:
            is_ok = False
            break
    if is_ok:
        print(cost)
        exit()
print(-1)

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)]

ans = 10**9
for i in range(2**n):
    cost = 0
    an = np.array([0]*m)
    for j in range(n):
        if (i >> j) & 1:
            cost += ca[j][0]
            an = an + np.array(ca[j][1:])
    
    if not np.any(an < x):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,X = LI()
CA = np.array([LI() for _ in range(N)])
ans = float('INF')
for i in range(2**N):
    bit = np.array([[i>>j&1 for j in range(N)]]).T
    temp = np.sum(CA*bit,axis=0).tolist()
    temp2 = []
    temp2.append(temp)
    for money,*x in temp2:
        for y in x:
            if y<X:
                break
        else:
            ans = min(ans,money)
print(ans if ans !=float('INF') else -1)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
c_list = [list(map(int,input().split())) for _ in range(N)]
cost_list = []
for i in range(2**N):
  achive = [0]*M
  achive_list = [0]*M
  cost = 0
  for j in range(N):
    if ((i>>j)&1)==1:
      cost = cost + c_list[j][0]
      for k in range(M):
        achive[k] = achive[k] + c_list[j][k+1]
        if achive[k] >= X:
          achive_list[k] = -1
  if sum(achive_list) == -1*M:
    cost_list.append(cost)
print(min(cost_list) if cost_list else -1)

Submission status: Accepted

Solution code:
cost = 10**9
N = 0
M = 0
X = 0

def solve(no, yn, book):
    global N, M, X, cost
    if no == N:
        understand = [0 for i in range(M)]
        c=0
        for i in range(len(yn)):
            if yn[i] == "Y":
                c += book[i][0]
                for j in range(M):
                    understand[j] += book[i][j+1]

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

        if possible:
            if cost > c:
                cost = c

    else:
        solve(no+1, yn+"Y", book)
        solve(no+1, yn+"N", book)

def main():
    global N, M, X, cost
    N, M, X = map(int, input().split())
    book = list()

    for i in range(N):
        b = [int(a) for a in input().split()]
        book.append(b)

    solve(0, "", book)
    if cost == 10**9:
        print(-1)
    else:
        print(cost)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N, M, X = [int(_) for _ in input().split()]
B = []
for i in range(N):
    B.append([int(_) for _ in input().split()])
l = [i for i in range(N)]
NUM = (10**5) * 12 + 1
ans = NUM
for i in range(1, N+1):
    C = itertools.combinations(l, i)
    for c in C:
        amount = 0
        U = [0 for i in range(M)]
        for k in range(i):
            amount += B[c[k]][0]
            for j in range(M):
                U[j] += B[c[k]][j+1]
        if min(U) >= X:
            ans = min(ans, amount)
if ans == NUM:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

# input
n, m, x = map(int, input().split())
c = [-1 for _ in range(n)]
a = [[-1 for _ in range(m)] for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    a[i] = tmp[1:]

# calc
# k冊買うとして全探索
ans = []
for k in range(n+1):
    seq = list(itertools.combinations(list(range(n)), k)) 
    for l in seq:
        rikaido = [0 for _ in range(m)]
        cost = 0 
        for i in l:
            cost += c[i]
        for p in range(m):
            for q in l:
                rikaido[p] += a[q][p]
        #print('rikaido = ', rikaido)
        ok = True
        for p in range(m):
            if rikaido[p] < x:
                ok = False
                break
        if ok: 
            ans.append(cost)

if len(ans) > 0:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

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

mini_money = (10**5)*12 + 1

for i in range(2 ** N):
    rikai = [0]*M
    money = 0
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            money += C_A[j][0]
            for k in range(M):
                rikai[k] += C_A[j][k+1]
                #print(money,C_A[j])

    if min(rikai) >= X:
        mini_money = min(money,mini_money)
        #print(mini_money)

if mini_money == (10**5)*12+1:
    print("-1")
else:
    print(mini_money)

Submission status: Accepted

Solution code:
N, M, X = [int(x) for x in input().split()]


C = []
RIKAI = []
ans = 0

BOOK= []
for i in range(N):
    BOOK += [[int(x) for x in input().split()]]

ans = -1
MIN_PAY = 10**5 * 12 +1

for FLAG in range(2 ** N ):
    PAY = 0
    RIKAI = [0] * M
    for i in range(N):
        if FLAG >> i & 1:
            for j in range(M):
                RIKAI[j] = RIKAI[j] + BOOK[i][j+1]
            PAY += BOOK[i][0] 
    if min(RIKAI) >= X:
        MIN_PAY = min(PAY,MIN_PAY)
        

if MIN_PAY == 10 ** 5 * 12 +1:
    ans = -1
else:
    ans = MIN_PAY

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m, x = map(int, input().split())
c = []
a = []

for i in range(n):
    a.append(list(map(int, input().split())))
    c.append(a[-1].pop(0))

l = list(product([0, 1], repeat=n))
ans = [] * len(l)

for t in range(len(l)):
    s = [0] * m
    for i in range(n):
        for j in range(m):
            s[j] += l[t][i]*a[i][j]
    if min(s) >= x:
        ans_n = 0
        for i in range(n):
            ans_n += l[t][i]*c[i]
        ans.append(ans_n)

if len(ans) > 0:
    print(min(ans))
else:
    print(-1)