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

n, m, x = (int(each) for each in input().split())

books = []
for i in range(n):
    books.append([int(each) for each in input().split()])

# print(books)

scores = []
products = itertools.product([0,1], repeat=n)
for pro in products:
    score = [0]*(m+1)
    for index, j in enumerate(pro):
        if j == 1:
            score = [x+y for (x, y) in zip(score, books[index])]
    if min(score[1:]) >= x:
        scores.append(score)

if len(scores) == 0:
    print(-1)
else:
    print(min([each[0] for each in scores]))

Submission status: Accepted

Solution code:
import itertools
N,M,X = map(int,input().split())
costs = []
books = []
for _ in range(N):
    entry = list(map(int,input().split()))
    costs.append(entry[0])
    books.append(entry[1:])
    
mxcost = sum(costs) + 1
lst = [list(i) for i in itertools.product([0, 1], repeat=N)]
for item in lst:
    cost = sum([item[0]*item[1] for item in zip(costs,item)])
    Xs = [0] * M
    for i in range(N):
        if item[i] == 1:
            for j in range(M):
                Xs[j] += books[i][j]
    if min(Xs) >= X:
        mxcost = min(mxcost,cost)

if mxcost == sum(costs) + 1:
    print(-1)
else:
    print(mxcost)

Submission status: Accepted

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

def tas(l1,l2):
    l3=[]
    for i in range(m+1):
        l3.append(l1[i]+l2[i])
    return l3


ll=[[0 for i in range(m+1)]]
for i in range(n):
    for j in range(len(ll)):
        ll.append(tas(ll[j],l[i]))

lm=[]
for i in ll:
    lll=[]
    for j in range(1,len(i)):
        if i[j]>=x:
            lll.append(True)
        else:
            lll.append(False)
    if all(lll)==True:
        lm.append(i[0])

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

Submission status: Accepted

Solution code:
import itertools

n,m,x=map(int,input().split())
c=[0]*n
a=[[0]*m for i in range(n)]
for i in range(n):
    l=list(map(int,input().split()))
    c[i]=l[0]
    a[i]=l[1:len(l)]
    
cmin=10**7
yn2=""
for i in itertools.product([0,1], repeat=n):
    csum=0
    yn=""
    asum=[0]*m
    for ii in range(len(i)):
        if i[ii]==1:
            for j in range(m):
                asum[j]+=a[ii][j]
            csum+=c[ii]
    for j in range(m):        
        if asum[j]<x:
            yn="no"
            break
    if yn!="no":
#        print(csum,cmin)
        cmin=min(cmin,csum)
        yn2="yes"

if yn2=="yes":
    print(cmin)                
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
C = np.array([[int(i) for i in input().split()] for j in range(N)])

memo = np.array([0 for i in range(M)])

def check(memo):
    for i in memo:
        if i < X:
            return False
    return True

def rec(i, cost, memo):
    if i == N:
        if check(memo):
            return cost
        return float("inf")
    
    # i番目を選ばない    
    # i番目を選ぶ
    return min(rec(i+1, cost, memo), rec(i+1, cost+C[i, 0], memo+C[i, 1:]))

ans = rec(0, 0, memo)
if ans != float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

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

cost = 10**12

import itertools

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


for i in S:
    cnt = 0
    ablity = [0] * M
    for j in range(N):
        if i[j] == 1:
            for k in range(M+1):
                if k == 0:
                    cnt += L[j][k]
                    
                else:
                    ablity[k-1] += L[j][k]
    
    ans = True
    for i in ablity:
        if i < X:
            ans = False
    
    if ans:
        cost = min(cost,cnt)
        
if cost == 10**12:
    print(-1)
else:
    print(cost)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

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

U = [0] * (M + 1)
def rec(ans, pos):
    if pos == N:
        return ans
    row = Matrix[pos]
    for i in range(M  + 1):
        U[i] += row[i]

    for u in U[1:]:
        if u < X:
            ans = min(rec(ans, pos + 1), ans)
            break
    else:
        ans = min(U[0], ans)

    for i in range(M  + 1):
        U[i] -= row[i]
    return min(rec(ans, pos + 1), ans)

ans = rec(float('inf'), 0)
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(n)]
ans = 10 ** 9
for i in range(2 ** n):
    sumA = [0 for i in range(m)]
    cost = 0
    for j in range(n):
        if ((i >> j) & 1):
            cost += C[j][0]
            for k in range(m):
                sumA[k] += C[j][k + 1]
    flag = True
    for l in range(m):
        if sumA[l] < x:
            flag = False
            break
    if flag:
        ans = min(ans, cost)
        
if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    import numpy as np

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

    Z = [list(format(i, '0{}b'.format(N))) for i in range(2**N)]

    cost = np.inf
    for z in Z[1:]:
        ind = np.array(z) == '1'
        ca = np.sum(CA[np.where(ind)], axis=0)
        if np.sum(ca[1:] >= X) == M:
            cost = min(cost, ca[0])
    if cost == np.inf:
        cost = (-1)
    print(cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
N,M,X=list(map(int,(stdin.readline().strip().split())))
cost=[]
money=0
und=[0]*M
sankousho=[]
for i in range(N):
    book = list(map(int, (stdin.readline().strip().split())))
    sankousho.append(book)
def hantei(und):
    for i in und:
        if i<X:return False
    return True
def kiroku(b,und):
    for i in range(M):
        und[i]+=b[i+1]
    return und
def use(book,i,money,und):
    money_A=money
    money_B=money
    und_A=und.copy()
    und_B=und.copy()
    if i==N:
        if hantei(und):
            cost.append(money)
    else:
        und_A=kiroku(book[i],und_A)
        money_A+=book[i][0]
        use(book,i+1,money_A,und_A)
        use(book,i+1,money_B,und_B)

use(sankousho,0,0,und)
if len(cost)==0:print(-1)
else:print(min(cost))

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = (int(i) for i in input().split())  
arr = []
c_list = []
for _ in range(N):
  A = [int(i) for i in input().split()] 
  c_list.append(A[0])
  arr.append(A[1:])

comb_list = []
def recur(N, lis):
  comb_list.append(lis)
  if len(lis) == N:
    return
  
  for i in range(lis[-1]+1, N):
    recur(N, lis + [i])  

for i in range(N):
  recur(N, [i])

ans = np.inf
for Z in comb_list:
  tmp = np.zeros(M)
  tmp_c = 0
  for z in Z:
    tmp += arr[z]
    tmp_c += c_list[z]
  if np.all(tmp >= X):
    ans = min(ans, tmp_c)

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

Submission status: Accepted

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

A = []
C = []

for i in range(N):
	tmp = [int(i) for i in input().split(' ')]
	C.append(tmp[0])
	A.append(tmp[1:])

import itertools
count = -1
m_li = []
lis = list(range(N))
for i in range(1, N+1):
	for pair in itertools.combinations(lis, i):
		count += 1
		money = 0
		Ad = [0]*M
		for j in pair:
			money += C[j]
			for ind,k in enumerate(A[j]):
				Ad[ind] += k
              	
		flag = True
		for j in range(M):
			if Ad[j]<X:
				flag = False
		if flag:
			m_li.append(money)

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m,x = map(int, input().split())
book = list()*n
for i in range(n):
    temp = input().split()
    book.append(temp)

matrix = np.array(book, dtype="int")
decide = np.array(list(itertools.product([True,False],repeat=n)))
decide = decide[:-1]
money = -1
for i in range(len(decide)):
    test = np.sum(matrix[np.where(decide[i,:]),:], axis = 0)
    test = np.sum(test, axis = 0)
    #print(test)
    #print(test[0])
    #print(np.sum(test[1:]>=x))
    if np.sum(test[1:]>=x) == m and (money > test[0] or money == -1):
        #print("koko")
        money = test[0]
if money == 1e6:
    print("-1")
else :
    print(money)

Submission status: Accepted

Solution code:
import numpy as np

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

for _ in range(N):
    row = list(map(int, input().split()))
    C, A = row[0], row[1:]
    Cs.append(C)
    As.append(A)

As = np.array(As)

for i in range(2 ** N):
    tmp_A = np.array([0] * M)
    tmp_ans = 0
    for j in range(N):
        if (i >> j) & 1:
            tmp_ans += Cs[j]
            tmp_A += As[j]
    cnt = 0
    for j in range(M):
        if tmp_A[j] >= X:
            cnt += 1
    if cnt == M:
        ans = min(ans, tmp_ans)

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

Submission status: Accepted

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


ans = float("inf")

for bit in range(1 << n):
    count = 0
    sum = [0]*m
    for i in range(n):
        if bit & (1 << i):
          for j in range(1,m+1):
            sum[j-1] += ca[i][j]
          count+=ca[i][0]
    for i in range(m):
      if sum[i]<x:
        break
      if i+1==m:
        ans=min(count,ans)
if ans==float("inf"):
  print(-1)
  exit()
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca_list = []
budget_list = []

for _ in range(n):
  ca_list.append(input())

for i in range(2 ** n):
  bit_list = []
  for j in range(n):
    if (i >> j) & 1:
      bit_list.append(j)
  #print(bit_list)
  budget = 0
  point_list = [0] * m
  for b in bit_list:
    text = list(map(int, ca_list[b].split()))
    point_list = [x + y for (x, y) in zip(text[1:], point_list)]
    budget += text[0]
  #print(budget, point_list)
  if min(point_list) >= x:
    budget_list.append(budget)

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

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = list(map(int, input().split()))
a_list = []
c_list = []
for _ in range(n):
  _a_list = list(map(int, input().split()))
  a_list.append(_a_list[1:])
  c_list.append(_a_list[0])

def ok(a_l):
  if a_l and min(np.sum(a_l, axis=0))>=x:
    return True
  else:
    return False

def dfs(l, i):
  if i==len(a_list) and not ok(l):
    return -1
  elif ok(l):
    return 0
  left = dfs(l+[a_list[i]], i+1)
  right = dfs(l, i+1)
  if left>=0 and right>=0:
    if left + c_list[i]<right:
      return left + c_list[i]
    elif left + c_list[i]>=right:
      return right
  elif left>=0 and right<0:
    return left + c_list[i]
  elif left<0 and right>=0:
    return right
  else:
    return min(left, right)

print(dfs([], 0))

Submission status: Accepted

Solution code:
import itertools
ans_li = []
n,m,x = map(int,input().split())
li = []
for _ in range(n):
    li.append(list(map(int,input().split())))

for i in range(n):
    if i == 0:
        tmp = [kkk for kkk in range(n)]
        #print(tmp)
        #score_li = [0]*m
        #okane = 0
        #print([k for k in range(n)],i+1,tmp)
        for t in tmp:
            score_li = [0]*m
            okane = 0
            #print(li,t,'ttttt')
            for ii,ll in enumerate(list(li[t])):
                if ii==0:
                    okane += li[t][ii]
                else:
                    #print(score_li,ii,ll)
                    score_li[ii-1]+=ll
            flag = True
            #print(score_li,okane)
            for ss in score_li:
                if ss<x:
                    flag = False
            if flag:
                ans_li.append(okane)

    else:
        tmp = list(itertools.combinations(range(n), i+1))
        #print(tmp)
        #score_li = [0]*m
        #okane = 0
        #print([k for k in range(n)],i+1,tmp)
        for t in tmp:
            score_li = [0]*m
            okane = 0
            #print(li,t,'ttttt')
            for aaa in t:
                for ii,ll in enumerate(list(li[aaa])):
                    if ii==0:
                        okane += li[aaa][ii]
                    else:
                        #print(score_li,ii,ll)
                        score_li[ii-1]+=ll
            flag = True
            for ss in score_li:
                if ss<x:
                    flag = False
            if flag:
                ans_li.append(okane)
#print(ans_li)
if len(ans_li)>0:
    print(min(ans_li))
else:
    print(-1)

Submission status: Accepted

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

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

li = [f'{i:012b}' for i in range(2**N)]
C = []
A = []
for i in range(N):
    B = list(map(int, input().split()))
    C.append(B[0])
    A.append(B[1:])

d = []
for l in li:
    b = l[::-1][:N]
    rikai = [0]*M
    pri = [0]*N
    for i in range(len(b)):
        if b[i] == '1':
            for j in range(M):
                rikai[j] += A[i][j]
            pri[i] += C[i]
    d.append((sum(pri), rikai))

ans = 10**100
for s in d:
    f = True
    for r in s[1]:
        if r < X:
            f = False
            break
    if f:
        ans = min(ans, int(s[0]))
if ans == 10**100:print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
ans = -1
arr = []
# 理解度Xを超えるような組み合わせをすべて列挙し、そのうちの最小金額を出力する
for _ in range(N):
    arr.append(list(map(int, input().split())))

for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        for i11 in range(2):
                                            for i12 in range(2):
                                                tmp_min = 0
                                                tmp_arr = [0] * M
                                                arr_cnt = 0
                                                N_cnt = 0
                                                while N > N_cnt:
                                                    if N_cnt == 0 and bool(i1):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 1 and bool(i2):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 2 and bool(i3):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 3 and bool(i4):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 4 and bool(i5):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 5 and bool(i6):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 6 and bool(i7):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 7 and bool(i8):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 8 and bool(i9):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 9 and bool(i10):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 10 and bool(i11):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    if N_cnt == 11 and bool(i12):
                                                        tmp_min += arr[arr_cnt][0]
                                                        for i in range(M):
                                                            tmp_arr[i] += arr[arr_cnt][
                                                                i + 1
                                                            ]

                                                    arr_cnt += 1
                                                    N_cnt += 1
                                                if min(tmp_arr) >= X:
                                                    if ans == -1:
                                                        ans = tmp_min
                                                    else:
                                                        ans = min(tmp_min, ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

l = []
for i in range(N):
    l += [np.array(list(map(int, input().split()))).reshape((M + 1, 1))]

r = np.array([0] * (M + 1)).reshape((M + 1, 1))

for x in l:
    r = np.concatenate([r, r + x], axis=1)

fitted = r[:, np.all(r[1:] >= X, axis=0)]

print(min(fitted[0]) if fitted.shape[1] != 0 else -1)

Submission status: Accepted

Solution code:
import itertools

n, m, x = map(int, input().split())
a_list = []
for _ in range(n):
    lst = list(map(int, input().split()))
    a_list.append(lst)
# print(c_list)
# print(a_list)

money = 0
skill = [0]*n
for i in range(n):
    money += a_list[i][0]
    skill = [x+y for (x, y) in zip(skill, a_list[i][1:])]
# print(skill)
for s in skill:
    if s < x:
        print(-1)
        exit()

ans = 100100100
for i in range(1, n+1):
    comb = list(itertools.combinations(a_list, i))
    # print(i, comb)
    for c in comb:
        money = 0
        skill = [0]*n
        for a in c:
            money += a[0]
            skill = [x+y for (x, y) in zip(skill, a[1:])]

        if min(skill) >= x:
            ans = min(ans, money)
print(ans)

Submission status: Accepted

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

cost=[]
rikai=[]
for i in range(n):
  temp=list(map(int,input().split()))
  cost.append(temp[0])
  rikai.append(temp[1:])

ans=10**10
for i in range(1,2**n):
  c=0
  t=[0]*m
  for j in range(n):
    if (i>>j) & 1:
      c+=cost[j]#j冊目の参考書
      for k in range(m):#ｋ番目の教科
        t[k]+=rikai[j][k]
      
  for l in t:
    if l < x:
      break
  else:
    ans=min(ans,c)
if ans != 10**10:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools as t
n,m,z=map(int,input().split())
l=[]
answer=set([])
for i in range(n):
    l.append(list(map(int, input().split())))
for k in range(n+1):
    a=list(t.combinations(range(n),k))
    for x in a:
        w=0
        A=[0 for _ in range(m)]
        s=0
        for y in x:
            w+=l[y][0]
            for k in range(m):
                A[k]+=l[y][k+1]
        for u in A:
            if u<z:
                s=1
        if s==0:
            answer.add(w)
if answer:
    print(min(answer))
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, m, x = LI()
    ca = LIR(n)
    ans = inf
    for mask in range(1 << n):
        tmp = [0] * m
        t = 0
        for i in range(n):
            if mask & (1 << i):
                for j in range(m):
                    tmp[j] += ca[i][j + 1]
                t += ca[i][0]
        if sum(map(lambda a: a < x, tmp)):
            continue
        ans = min(ans, t)
    if ans == inf:
        print(-1)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,M,X= map(int,input().split())
m = 10000000

A = [[0 for i in range(M)]for i in range(N)]
C=[0]*(2**N)
for i in range(N):
    A[i] = list(map(int,input().split()))
for i in range(2 ** N):
    Ad = []
    for j in range(N):
        if (i >> j) & 1  == 1:
            Ad.append(A[j])

    
    xs = [0]*(M+1)
    for k in range(len(Ad)):
        C[i]+=Ad[k][0]
        for l in range(1,M+1):
            xs[l] += Ad[k][l]      
        
    flag = True

    for l in range(1,M+1):
        if xs[l] >= X:
            continue
        else:
            flag = False
            

    if flag and m > C[i]:

        m = C[i]

if m < 10000000:
    print(m)
else:
    print(-1)

Submission status: Accepted

Solution code:
INF = 1001001001
N, M, X = map(int, input().split())
C, A = [], []
for i in range(N):
    _c = list(map(int, (input().split())))
    _a = _c[1:]
    _c = _c[0]
    A.append(_a)
    C.append(_c)
ans = INF
for b in range(1<<N):
    money = 0
    point = [0]*M
    for i in range(N):
        if (b>>i)&1:
            money += C[i]
            for j in range(M):
                point[j] += A[i][j]
    for j in range(M):
        if point[j] < X:
            break
    else:
        ans = min(ans, money)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def C():
    n, m, x = map(int, input().split())
    books = [tuple(map(int, input().split())) for i in range(n)]
    books = list(zip(*books))
    res = []
    for i in range(2**n):
        flag = True
        pattern = list(map(int, bin(i)[2:].zfill(n)))
        for j in range(m):
            skill = sum(map(lambda x,y: x*y, pattern, books[j+1]))
            if skill < x:
                flag = False
                break
        if flag:
            cost = sum(map(lambda x,y: x*y, pattern, books[0]))
            res.append(cost)
    if res != []:
        print(min(res))
    else:
        print(-1)
C()

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
books = [list(map(int,input().split())) for _ in range(N)]
digit = "0"+str(N)+"b"
ans = float("INF")
for i in range(2**N):
    flags = list(format(i,digit))
    rikaid = [0]*(M)
    cost = 0
    for j in range(N):
        if flags[j] == "1":
            cost += books[j][0]
            for k in range(M):
                rikaid[k] += books[j][k+1]
    for r in rikaid:
        if r < X:
            break
    else:
        ans = min(ans,cost)
if ans == float("INF"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m, x = MAP()
bene = [[0]*(m+1) for i in range(n)]
for i in range(n):
    a = LIST()
    bene[i] = a

def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

bene = sorted(bene)
result = []
for n in range(1,len(bene)+1):
    for conb in itertools.combinations(bene, n):
        conb = list(conb)
        res = conb[0]
        for i in range(len(conb)-1):
            res = add(res, conb[i+1])
        result.append(res) 
result = sorted(result)

for i in range(len(result)):
    flag = True
    for j in range(m):
        if result[i][j+1] <x:
            flag = False
    if flag:
        print(result[i][0])
        sys.exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18
#list(map(int, stdin.readline().rstrip().split()))
n,m,x = map(int, stdin.readline().rstrip().split())
numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]

rikai = [0] * m
l = [i for i in range(1,n+1)]
ans = 10**9
for i in l:
    books = list(comb(l,i))

    for j in books:
        # jを選ぶ
        pay = 0
        rikaii = rikai[:]
        for u in j:
            cost = numbers[u-1][0]
            skill = numbers[u-1][1:]
            pay += cost
            rikaii = [x + y for (x, y) in zip(rikaii, skill)]
        ok = 0
        for y in range(m):
            if rikaii[y] >= x:
                ok += 1
        if ok == m:
            ans = min(ans,pay)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
AC = [[0 for i in range(M + 1)] for j in range(N)]
for i in range(N):
  AC[i] = list(map(int, input().split()))
x = 2 ** N
ans = -1
for i in range(x):
  p = i
  A = [0] * M
  summ = 0
  for j in range(N):
    y = p // (2 ** (N - j - 1))
    p = p -  (y * (2 ** (N - j - 1)))
    if y == 1 :
      summ = summ + AC[j][0]
      for k in range(M):
        A[k] = A[k] + AC[j][k + 1]
  tip = 0
  for j in range(M):
    if A[j] < X:
      tip = 1
  if tip == 0:
    if (ans == -1):
      ans = summ
    elif summ < ans:
      ans = summ
print(ans)