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:
def solve(L):
    cost = 0
    s = [0] * m
    for k in range(n):
        if L[k] == 1:
            cost += A[k][0]
            for l in range(1, m+1):
                s[l-1] += A[k][l]
    if all(s[i] >= x for i in range(m)):
        return cost
    else:
        return float('inf')

n, m, x = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')
for i in range(2 ** n):
    L = [0] * n
    for j in range(n):
        if ((i >> j) & 1) != 0:
            L[j] = 1
    ans = min(ans, solve(L))
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,X = list(map(int,input().split()))
CA = [list(map(int,input().split())) for _ in range(N)]
options = itertools.product([0,1],repeat=N)
mincost = float('inf')
for o in options:
    XL = [X]*M
    cost = 0
    for i in range(N):
        if o[i] == 1:
            cost += CA[i][0]
            for j in range(M):
                XL[j] -= CA[i][j+1]
    if len(list(filter(lambda x: x > 0,XL))) == 0:
        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())

A = [0]*N

for i in range(N):
	A[i] = list(map(int, input().split()))

cost = 100000*12
ans = -1

for i in range(2**N):
	total = [0]*(M)
	c = 0
	for j in range(N):
		if ((i >> j) & 1):
			c += A[j][0]
			count = 0
			for k in range(M): 
				total[k] += A[j][k + 1]
	if min(total) >= X:
		cost = min(cost, c)
		ans = cost

print(ans)

Submission status: Accepted

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

ans=float('inf')

for x in range(2**N):
   b=format(x,'b').zfill(N)
   cost=0
   A=[0]*(M+1)
   flag=[0]*(M+1)
   for i,n in enumerate(b):
      if n=='1':
         cost+=c_a[i][0]
         for j in range(1,M+1):
            A[j]+=c_a[i][j]
            if A[j]>=X: flag[j]=1
   if sum(flag)==M:
      ans=min(ans,cost)
if ans==float('inf'): print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
def list_add(li1, li2):
    return list(map(sum, zip(li1, li2)))


def dfs(price, knowledge, depth):
    if (min(knowledge) >= X):
        ansList.append(price)
    if depth == N:
        return
    dfs(price, knowledge, depth + 1)
    dfs(price + priceList[depth],
        list_add(KnowList[depth], knowledge), depth + 1)


N, M, X = map(int, input().split(" "))
KnowList = [[] for i in range(N)]
priceList = [0] * N
for i in range(N):
    tmp = [int(i) for i in input().split(" ")]
    priceList[i] = tmp[0]
    KnowList[i] = tmp[1:]
price = 0
ansList = []
knowledge = [0] * M
dfs(price, knowledge, 0)
if (len(ansList) == 0):
    ansList.append(-1)
print(min(ansList))

Submission status: Accepted

Solution code:
def list_add(li1, li2):
    return list(map(sum, zip(li1, li2)))


def dfs(price, knowledge, depth):
    if (min(knowledge) >= X):
        ansList.append(price)
    if depth == N:
        return
    dfs(price, knowledge, depth + 1)
    dfs(price+priceList[depth], list_add(KnowList[depth], knowledge), depth+1)


N, M, X = map(int, input().split(" "))
KnowList = [[] for i in range(N)]
priceList = [0] * N
for i in range(N):
    tmp = [int(i) for i in input().split(" ")]
    priceList[i] = tmp[0]
    KnowList[i] = tmp[1:]
price = 0
ansList = []
knowledge = [0] * M
dfs(price, knowledge, 0)
if (len(ansList) == 0):
    ansList.append(-1)
print(min(ansList))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = []

for _ in range(N):
    C, *A = map(int, input().split())
    CA.append((C, A))

ans = 10**9
for i in range(2**N):
    flag = True
    tmp_C = 0
    tmp_A = [0]*M
    for j in range(N):
        if i >> j & 1:
            tmp_C += CA[j][0]
            for k in range(M):
                tmp_A[k] += CA[j][1][k]
    for tmp_a in tmp_A:
        if tmp_a < X:
            flag = False
            break
    if flag == True:
        ans = min(ans, tmp_C)

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

Submission status: Accepted

Solution code:
def CanIGetEnoughSkills(SkillPoints,M,X):
    for _ in range(M):
        if SkillPoints[_]<X:
            return False
        else:
            pass
    return True


N,M,X=map(int,input().split())
books=[]
for n in range(N):
    array= list(map(int,input().split()))
    books.append(array)
# print(books)

BookCost=[]
GetSkillPoints=[]
for i in range (N):
    BookCost.append(int(books[i][0]))
    GetSkillPoints.append(books[i][1:])

temp_cost=10**9

for Cart in range (2**len(GetSkillPoints)):
    TotalCost=0
    SkillPoints=[0]*M
    
    for book in range(len(GetSkillPoints)):
        if (Cart>>book)&1==0:
            continue
        TotalCost+= BookCost[book]
        for skillelement in range(M):
            SkillPoints[skillelement]+=GetSkillPoints[book][skillelement]

    # print(TotalCost,SkillPoints)
    if CanIGetEnoughSkills(SkillPoints,M,X)== True:
        temp_cost=min(temp_cost,TotalCost)

Answer=temp_cost
if Answer==10**9:
    Answer=-1
    
print(Answer)

Submission status: Accepted

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

cost = []
data = []

for _ in range(n):
    tmp = [int(x) for x in input().split()]
    cost.append(tmp[0])
    data.append(tmp[1:])

ans = 1200010

for i in range(1<<n):
    tmpcost = 0
    xarr = [0]*m
    for j in range(12):
        if (i&(1<<j)):
            tmpcost+=cost[j]            
            for k in range(m):
                xarr[k] += data[j][k]

    xarr = [val >= x for val in xarr]
    if all(xarr):ans = min(ans,tmpcost)



if ans == 1200010:print(-1)
else:print(ans)

Submission status: Accepted

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

book = []

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

min_cost = 9999999
  
for i in range(1,2**n):
  b = format(i, 'b')
  b = b.zfill(n)
  cost = 0
  us = [0 for _ in range(m)]
  for j in range(len(b)):
    if int(b[j]) == 1:
      cost += book[j][0]
      for k in range(m):
        us[k] += book[j][k+1]
  
  if sum(a>=x for a in us) == m:
    if cost < min_cost:
      min_cost = cost

if min_cost == 9999999:
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

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

price = []
point = []

for i in range(n):
    book = list(map(int, input().split()))
    price.append(book[0])
    point.append(book[1:])

s = -1

for i in range(2**n):
    buy_price = 0
    buy_point = [0] * m
    for j in range(n):
        if i >> j & 1:
            buy_price += price[j]
            for k in range(m):
                buy_point[k] += point[j][k]

    if all([l >= x for l in buy_point]):
        if s > buy_price or s < 0:
            s = buy_price

print(s)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
clis=[]
alis=[]
for _ in range(n):
  tu=list(map(int,input().split()))
  clis.append(tu[0])
  alis.append(tu[1:])


ma_c=[]
for i in range(2**n):
  bag=[]
  price=0
  for j in range(n):
    if ((i>>j)&1):
      price+=clis[j]
      bag.append(alis[j])
  pac=[0]*m
  for t in range(len(bag)):
    for k in range(m):
        pac[k]+=bag[t][k]
  if all([pac[t]>=x for t in range(m)]):
    ma_c.append(price)


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

Submission status: Accepted

Solution code:
import itertools
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
B = list(itertools.product([0,1], repeat=N))#bit探索
sums = {}
anss = []
for i in range(N):
    for b in B:#直積を使う
        #print(b)#BITで増えていく仕組み
        #print(sums)
        #print(anss)
        ans = 0
        Point = [0]*M
        #print(Point)
        count = 0
        for z in b:
            #print(z)#bの中の内容を１つづつやっているのと一緒
            if z == 1:
                for k in range(M):
                    Point[k] += A[count][k+1]
                ans += A[count][0]
                #print(Point)
                if M == len([Point[n] for n in range(M) if Point[n] >= X]):
                    #何一つもXより大きいかという条件を外れてはいけない
                    anss.append(ans)
            count += 1
if len(anss) != 0:
    print(min(anss))
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

N,M,X = map(int,input().split())
C = [list(map(int,input().split())) for n in range(N)]
cost = 10**9

for com in itertools.chain(*(itertools.combinations(C,r) for r in range(1,N+1))):
    c,*a = map(sum,zip(*com))
    if c<cost and X<=min(a):
        cost = c

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

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
list1 = list(range(N))
list2 = []
book = [list(map(int, input().split())) for _ in range(N)]

com = 0
for i in range(1,N+1):
  listi = list(itertools.combinations(list1, i))
  list2.extend(listi)

anslist = []
for i in range(len(list2)):
  anslistnew = [0] * (M+1)
  for j in range(len(list2[i])):
    for k in range(M+1):
      anslistnew[k] += book[list2[i][j]][k]
  for l in range(1, M+1):
    if anslistnew[l] < X:
      anslistnew[0] = 0
      break
  if anslistnew[0] > 0:
    anslist.append(anslistnew[0])
    
if anslist == []:
  print(-1)
else:
  print(min(anslist))

Submission status: Accepted

Solution code:
import itertools
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
B = list(itertools.product([0,1], repeat=N))
sums = {}
anss = []
for i in range(N):
    for b in B:
        ans = 0
        Point = [0]*M
        count = 0
        for z in b:
            if z == 1:
                for k in range(M):
                    Point[k] += A[count][k+1]
                ans += A[count][0]
                if M == len([Point[n] for n in range(M) if Point[n] >= X]):
                    anss.append(ans)
            count += 1
if len(anss) != 0:
    print(min(anss))
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c_list = [] 
a_list = []
for i in range(0, n):
  c, *a = map(int, input().split())
  c_list.append(c)
  a_list.append(a)
ans = float("inf")

for x1 in [0, 1]:
  for x2 in [0, 1]:
    for x3 in [0, 1]:
      for x4 in [0, 1]:
        for x5 in [0, 1]:
          for x6 in [0, 1]:
            for x7 in [0, 1]:
              for x8 in [0, 1]:
                for x9 in [0, 1]:
                  for x10 in [0, 1]:
                    for x11 in [0, 1]:
                      for x12 in [0, 1]:
                        if n == 1:
                          x_list = [x1]
                        elif n == 2:
                          x_list = [x1, x2]
                        elif n == 3:
                          x_list = [x1, x2, x3]
                        elif n == 4:
                          x_list = [x1, x2, x3, x4]
                        elif n == 5:
                          x_list = [x1, x2, x3, x4 ,x5]
                        elif n == 6:
                          x_list = [x1, x2, x3, x4 ,x5, x6]
                        elif n == 7:
                          x_list = [x1, x2, x3, x4 ,x5, x6, x7]
                        elif n == 8:
                          x_list = [x1, x2, x3, x4 ,x5, x6, x7, x8]
                        elif n == 9:
                          x_list = [x1, x2, x3, x4 ,x5, x6, x7, x8, x9]
                        elif n == 10:
                          x_list = [x1, x2, x3, x4 ,x5, x6, x7, x8, x9, x10]
                        elif n == 11:
                          x_list = [x1, x2, x3, x4 ,x5, x6, x7, x8, x9, x10, x11]
                        elif n == 12:
                          x_list = [x1, x2, x3, x4 ,x5, x6, x7, x8, x9, x10, x11, x12]
                        cost = 0
                        gaku_list = [0] * m
                        for i in range(0, n):
                          if x_list[i] == 1:
                            for j in range(0, m):
                              gaku_list[j] += a_list[i][j]
                            cost += c_list[i]
                        flag = 1
                        for gaku in gaku_list:
                          if gaku < x:
                            flag = 0
                            break
                        if flag == 1 and cost < ans:
                          ans = cost
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N,M,X = map(int,input().split())
item = [list(map(int,input().split())) for i in range(N)]
bag = []

for i in range(2**N):
  temp = []
  job = [0] * M
  for s in range(N):
    if (i>>s)&1:
      temp.append(s)
      for j in range(M):
        job[j] += item[s][j+1]
  for s in range(len(job)):
    if job[s]<X:
      break
  else:
    ans = 0
    for s in temp:
      ans += item[s][0]
    bag.append(ans)
print(min(bag) if len(bag)>=1 else -1)

Submission status: Accepted

Solution code:
import numpy as np

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

listC=[]
listall=[]

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

for i in range(2**N):
    total=np.zeros(M+1)
    for j in range(N):
        
        if ((i >> j) & 1):
            total=total+np.array(listC[j])
            #print(total)
    listall.append(list(total))
            


#print(listall)
ans=[]
for i in range(len(listall)):
    flag=True
    for j in range(M):
        if listall[i][j+1] < X:
            #print(j,listall[i][j+1])
            flag=False
        if j==(M-1) and flag==True:
            ans.append(listall[i][0])

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

Submission status: Accepted

Solution code:

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

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

minCost = sum(C)
exist = False

for i in range(2 ** N):
	rikai = [0] * M
	cost = 0
	for n in range(N):
		if i >> n & 1 == 0:
			cost+=C[n]
		
			for m in range(M):
				rikai[m]+=A[n][m]
	ok = True

	for m in range(M):
		if rikai[m] < X:
			ok = False

	if ok:
		exist = True
		minCost = min(minCost,cost)

if exist:
	print(minCost)
else:
	print(-1)

Submission status: Accepted

Solution code:
import operator
import functools
import itertools
import math


def sum_of_vector(vec1, vec2):
    return list(map(operator.add, vec1, vec2))


def powerset(iterable):
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s) + 1))


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

min_value = float("inf")
for x in powerset(books):
    if x:
        vec_sum = functools.reduce(sum_of_vector, x)
        cost, *achieves = vec_sum
        if all(map(lambda achieve: achieve >= X, achieves)):
            if min_value > cost:
                min_value = cost

if math.isinf(min_value):
    print(-1)
else:
    print(min_value)

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import combinations
N, M, X = map(int, input().split())
Array = [list(map(int,list(input().split()))) for i in range(N)]

Array.sort(key=itemgetter(0))
C = [i[0] for i in Array]
A = [i[1:] for i in Array]

#print(C,A)

cost = -1
for i in range(N):
    pt = list(combinations(range(N), i+1))
#    print(pt)
    for j in range(len(pt)):
        S = [0 for i in range(M)]
        Sc = 0
#        print("===")
        for k in pt[j]:
            S = [a + b for a, b in zip(A[k], S)]
            Sc += C[k]
#        print("---")
#        print(S)
#        print(Sc)
        
        if X<=min(S) and ((Sc < cost) or cost==-1):
           cost = Sc
print(cost)

Submission status: Accepted

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

aho = []  # ans[money, skill, skilll, skillll]
for i in range(2**n):
    buy = list(map(int, bin(i)[2:].zfill(n)))
    baka = [0] * (m+1)
    for j in range(n):
        if buy[j]:
            for k in range(m+1):
                baka[k] += c[j][k]
    judge = 1
    for j in baka[1:]:
        if j < x:
            judge = 0
    if judge:
        aho.append(baka)

if len(aho) == 0:
    print(-1)
else:
    print(sorted(aho)[0][0])

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(N)]
res = float('inf') #無限で初期化
for i in range(2**N):
    tca = [0]*(M+1) #index(0)=totalcost
    for j in range(N):
        if (i >> j) & 1:#その本を使うかどうかの判定
            for k in range(M+1):
                tca[k] += ca[j][k]
    if min(tca[1:]) >= X:
        res = min(res, tca[0])

if res != float('inf'):
    print(res)
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)]
res = float('inf') #無限で初期化
for i in range(2**N):
    tca = [0]*(M+1) #index(0)=totalcost
    for j in range(N):
        if i & (1 << j) > 0:#その本を使うかどうかの判定
            for k in range(M+1):
                tca[k] += ca[j][k]
    if min(tca[1:]) >= X:
        res = min(res, tca[0])

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
A = []
for i in range(N):
  line = list(map(int,input().split()))
  A.append(line)
def score(H):
  result = [0]*(M+1)
  for i in range(N):
    if H[i] == 1:
      for m in range(M+1):
        result[m] += A[i][m]
  if min(result[1:]) < X:
    return float('inf')
  else:
    return result[0]
def dfs(H):
  if len(H) == N:
    return score(H)
  res = float('inf')
  for v in range(2):
    H.append(v)
    res = min(res,dfs(H))
    H.pop()
  return res
ans = dfs([])
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(n)]
ans = 193934993409409
for mask in range(2 ** n):
    C = [0] * m
    cst = 0
    for i in range(n):
        if (mask >> i) & 1:
            cst += X[i][0]
            for j in range(1, m + 1):
                C[j - 1] += X[i][j]
    if min(C) >= x:
        ans = min(ans, cst)
if ans < 91912922191:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
answer = 0
judge = True
price = []
n,m,x = map(int,input().split())
ca = []
for i in range(n):
    ca.append(list(map(int, input().split())))
for i in range(2**n):
    judge = True
    choice_str = bin(i)
    now_x = []
    new_ca = 0
    for j in range(m):
        now_x.append(0)
    for j in range(len(choice_str)-2):
        choice_int = int(choice_str[-j-1])
        if choice_int == 1:
            for k in range(m):
                now_x[k] += ca[j][k+1]
    for j in range(m):
        if now_x[j] < x:
            judge = False
    if judge == True:
        for j in range(len(choice_str)-2):
            choice_int  = int(choice_str[-j-1])
            if choice_int == 1:
                new_ca += ca[j][0]
        price.append(new_ca)
if len(price) != 0: 
    answer = min(price)
else:
    answer = "-1"
print(answer)

Submission status: Accepted

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

import numpy as np
CA = np.array(CA)

import itertools
l = []
for i in range(1, N+1):
    for C in itertools.combinations(CA, i):
        if (sum(C)[1:N+1]>=X).all():
            l.append(sum(C)[0])

if l == []:
    print(-1)
else:
    print(min(l))

Submission status: Accepted

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

for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1): 
            bag.append(l[j])  
    skill=[0]*m
    enough=[0]*m 
    money=0
    for sub in bag:
        money+=sub[0]
        for kk in range(1,m+1):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enough[kk-1]+=1
    if 0 not in enough: 
        if ans>money:
            ans=money
if ans==99999999:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
mn = 1e9
k = 2 ** n
for i in range(k):
    c = 0
    subset = [0] * m
    for y in range(n):
        if i & 1 << y:
            c += l[y][0]
            for z in range(1, m + 1):
                subset[z - 1] += l[y][z]
    if all(h >= x for h in subset):
        mn = min(c, mn)
if mn == 1e9:
    print(-1)
else:
    print(mn)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [0] * n
a = [[0 for _ in range(m)] for q in range(n)]
for i in range(n):
    l = list(map(int, input().split()))
    c[i] = l[0]
    for w in range(m):
        a[i][w] = l[w + 1]
inf = float('inf')
ans=inf
for i in range(2 ** n):
    cost = 0
    e=[0]*m
    for j in range(n):
        if i >> j & 1:
            cost += c[j]
            for k in range(m):
                e[k] += a[j][k]
    ok=True
    for y in range(m):
        if e[y] < x:
            ok = False
            break
    if ok:
        ans = min(ans, cost)
print(ans if ans!=inf else '-1')

Submission status: Accepted

Solution code:
import numpy as np

n,m,x = map(int, input().split())
mat = []
for _ in range(n):
    mat.append(list(map(int,input().split())))
mat = np.array(mat)
min_cost = 10**5 *12+1
x_m = np.array([x]*m)
for i in range(2**n):
    sum_a = np.zeros((1,m), int)
    sum_c = 0
    for j in range(n):
        if ((i>>j)&1):
            sum_a += mat[j,1:]
            sum_c += mat[j,0]

    if np.sum(sum_a>=x_m)==m:
        if sum_c < min_cost:
            min_cost = sum_c

if min_cost > 10**5*12:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Book = [list(map(int, input().split())) for _ in range(N)]
List = [[0 for _ in range(M+1)] for _ in range(2**N)]
Min = float("inf")
for i in range(2**N):
  for j in range(N):
    if ((i >> j) & 1):
      for k in range(M+1):
        List[i][k] += Book[j][k]
      if Min > List[i][0] and min(List[i][1:]) >= X:
        Min = List[i][0]
if Min == float("inf"):
  print(-1)
else:
  print(Min)

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
Book = [[] for _ in range(N)]
mi = float('inf')
for i in range(N):
    Book[i] = list(map(int,input().split()))
for j in range(2**N):
    s = [0 for _ in range(N)]
    k = str(bin(j))[2:]
    o = len(k)
    x = 0
    f = 0
    B = [0 for u in range(M)]
    for l in range(o):
        s[N-l-1]= int(k[o-l-1])
    for p in range(N):
        if s[p] == 1:
            x += Book[p][0]
            for q in range(1,M+1):
                B[q-1] += Book[p][q]
    for n in range(M):
        if B[n] < X:
            break
        f += 1
    if x < mi and f == M:
        mi = x
if mi == float('inf'):
    print(-1)
    exit()
print(mi)

Submission status: Accepted

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

result = -1
for i in range(len(comb)):
    understand = [0]*m
    total_fee = 0
    for j in range(len(comb[i])):
        total_fee += comb[i][j][0]
        for k in range(m):
            understand[k] += comb[i][j][k+1]
    if all(t >= x for t in understand) and (result == -1 or result > total_fee):
        result = total_fee
 
print(result)

Submission status: Accepted

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

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

result = -1
for i in range(1 << n):
    t = [0] * m
    cost = 0
    for j in range(n):
        if(i >> j) & 1 == 0:
            continue
        cost += c[j]
        for k in range(m):
            t[k] += a[j][k]
    if all(X >= x for X in t):
        if result == -1:
            result = cost
        else:
            result = min(result, cost)
            
print(result)

Submission status: Accepted

Solution code:
N ,M, X = list(map(int,input().split()))
C = []
A = []
for i in range(N):
    B  = list(map(int, input().split()))
    C.append(B[0])
    A.append(B[1:])

money =[]
for i in range(2** N):
    tmp=[]
    for j in range(N):
        if ((i>>j)&1):
            tmp.append(C[j])
    money.append(sum(tmp))

result = [0 for i in range(2**N)]
for k in range(M):
    for i in range(2** N):
        tmp=[]
        for j in range(N):
            if ((i>>j)&1):
                tmp.append(A[j][k])
        if sum(tmp) >= X:
            result[i] +=1
book_price =[]
for i in range(len(result)):
    if result[i] == M:
        book_price.append(money[i])

if book_price:
    print(min(book_price))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, x = map(int, readline().split())
c = [list(map(int, readline().split())) for _ in range(n)]

ans = float('inf')
# bit全探索
for i in range(2 ** n):
    bag = [0]*(m+1)
    for j in range(n):
        if ((i >> j) & 1):
            bag = [x + y for (x, y) in zip(bag, c[j])]
        if min(bag[1::]) >= x:
            ans = min(ans, bag[0])
            
print('-1'if ans == float('inf') else int(ans))

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, x = map(int, readline().split())
c = [list(map(int, readline().split())) for _ in range(n)]

ans = float('inf')
# bit全探索
for i in range(2 ** n):
    bag = np.empty(m+1)
    total = 0
    for j in range(n):
        if ((i >> j) & 1):
            bag += np.array(c[j])
        if np.amin(bag[1::]) >= x:
            ans = min(ans, bag[0])
            
print('-1'if ans == float('inf') else int(ans))

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np


def main(N, M, X, C):
    min = 10000000000000
    for i in range(2**N):
        a = np.zeros(N)
        cost = 0
        for j in range(N):
            a[j] = (i//(2**j)) % 2
            if a[j] == 1:
                cost += C[j][0]
        for l in range(M):
            sum = 0
            for k in range(N):
                if a[k] == 1:
                    sum += C[k][l+1]
            if sum < X:
                break
            if l == M-1:
                if cost <= min:
                    min = cost
    return min


N, M, X = map(int, input().split())
C = [list(map(int, input().split()))for _ in range(N)]
ans = main(N, M, X, C)
if ans == 10000000000000:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
book = [list(map(int, input().split())) for _ in range(n)]
cos_min=10**10*n
for i in range(1,2**n):
    s_c= [0]*(m+1)
    choose = bin(i)[2:].zfill(n)

    for j in range(n):
        if choose[n-j-1]=="1":  
            s_c = [a+b for (a,b)in zip(s_c,book[j])]

    for j in s_c[1:]:
        if j<x:
            break
    else:
        cos_min=min(cos_min,s_c[0])

if cos_min!=10**10*n :
    print(cos_min)
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(n)]
choose = 1
cost_min = 10000000 * n
for i in range(2 ** n - 1):
    a_list = [0] * (m + 1)
    c = bin(choose)[2:].zfill(n)

    for j in range(n):
        if c[n - j - 1] == '1':
            a_list = [a + b for (a, b) in zip(a_list, book[j])]
    choose += 1
    
    for k in a_list[1:]:
        if k < x:
            break
    else:
        cost_min = min(cost_min, a_list[0])

if cost_min != 10000000 * n:
    print(cost_min)
else:
    print(-1)

Submission status: Accepted

Solution code:
INF=10000050

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

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

combination=[i for i in range(2**N)]

min_price=INF

for i in range(2**N):
    price=0
    knowledge=[0 for i in range(M)]
    for j in range(N):
        if combination[i]%(2**(j+1)):
            price+=C[j]
            for k in range(M):
                knowledge[k]+=A[j][k]
            combination[i]-=2**j
    if min(knowledge)>=X:
        min_price=min(min_price,price)

if min_price==INF:
    print("-1")
else:
    print(min_price)

Submission status: Accepted

Solution code:
INF=10000050

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

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

combination=[i for i in range(2**N)]

min_price=INF

for i in range(2**N):
    price=0
    knowledge=[0 for i in range(M)]
    for j in range(N):
        if combination[i]%(2**(j+1)):
            price+=C[j]
            for k in range(M):
                knowledge[k]+=A[j][k]
            combination[i]-=2**j
    if min(knowledge)>=X:
        min_price=min(min_price,price)

if min_price==INF:
    print("-1")
else:
    print(min_price)

Submission status: Accepted

Solution code:

n, m, x = map(int, input().split())
c, a = [0] * n, [0] * n
for i in range(n):
    c[i], *a[i] = map(int, input().split())
l = []
b = [[a[j][i] for j in range(n)] for i in range(m)]
nums = [("0"*n + bin(i)[2:])[-n:] for i in range(1, 2 ** n)]

for i in nums:
    if min(sum(k[j]*int(i[j]) for j in range(len(i))) for k in b) >= x:
        l.append(sum(c[j]*int(i[j]) for j in range(len(i))))
print(min(l) if l else -1)