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 pprint
N, M, X = [int(i) for i in input().split()]

books = {}
for i in range(N):
    hoge = list(map(int, input().split()))
    books[i] = hoge

Achievement = False  # 達成

for n in range(2 ** N):
    conditions = [0 for m in range(M + 1)]  # 条件
    for i in range(N):
        if ((n >> i) & 1):
            for m in range(M + 1):
                conditions[m] += books[i][m]

    # 条件が達成しているか判定
    count = 0
    for m in range(1, M + 1):
        if conditions[m] < X:
            break
        count += 1
    if count == M:
        if Achievement == False:
            Achievement = True
            min = conditions[0]
        elif min > conditions[0]:
            min = conditions[0]

if Achievement == False:
    print(-1)
else:
    print(min)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import copy

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

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


bss = [[ 0 for i in range(m + 1)]]
mc = -1

for i in range(n):
    nbss = copy.copy(bss)
    for bs in bss:
        #print(bs, b[i])
        nbs = list(map(lambda x, y: x + y, bs, b[i]))
        for j in range(1, m + 1):
            if nbs[j] < x:
                nbss.append(nbs)
                break
        else:
            if mc < 0:
                mc = nbs[0]
            else:
                mc = min(mc, nbs[0])
                
    bss = nbss

print(mc)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
ans=-1
t=[0]*(m+1)
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(2 ** n):
    for j in range(n):
        if (i >> j) & 1:
            for lnd,l in enumerate(a[j]):
                t[lnd]+=l
    if ans==-1 or ans > t[0]:
        if min(t[1:m+1]) >= x:
            ans = t[0]
    t=[0]*(m+1)
print(ans)

Submission status: Accepted

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

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

ans=float("inf")
for i in range(2**N):
    ans_temp=0
    f=True
    check=[0]*M
    for j in range(N):
        if (i>>j)&1:
            ans_temp+=A[j][0]
            for k in range(M):
                check[k]+=A[j][k+1]
    for l in check:
        if l<X:
            f=False
            break
    if f:
        ans=min(ans,ans_temp)

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

Submission status: Accepted

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

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

ans=float("inf")
for i in range(2**N):
    ans_temp=0
    f=True
    check=[0]*M
    for j in range(N):
        if (i>>j)&1:
            ans_temp+=A[j][0]
            for k in range(M):
                check[k]+=A[j][k+1]
    for l in check:
        if l<X:
            f=False
    if f:
        ans=min(ans,ans_temp)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []
A = []
result = -1

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

for n in range(1 << N):
    Cn = 0
    skill = [0] * M
    for i in range(N):
        if (n >> i) & 1 == 1:
            Cn += C[i]
            for j in range(M):
                skill[j] += A[i][j]

    if all(x >= X for x in skill):
        if result == -1:
            result = Cn
        else:
            result = min(result, Cn)

print(result)

Submission status: Accepted

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

ans = 10 ** 10

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

C = []
A = [[]] * N

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

for i in range(2 ** N):
    tans = 0
    tA = [0] * M
    for j in range(N):
        if i & (1 << j):
            tans += C[j]
            for k in range(M):
                tA[k] += A[j][k]

    flag = True
    for k in range(M):
        flag &= (tA[k] >= X)

    #print(i, tA, tans)

    if flag:
        ans = min(ans, tans)

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

Submission status: Accepted

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

ans = 10 ** 10

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

C = []
A = [[]] * N

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

# for i in range(2 ** N - 1):
for i in range(2 ** N):
    tans = 0
    tA = [0] * M
    for j in range(N):
        if i & (1 << j):
            tans += C[j]
            for k in range(M):
                tA[k] += A[j][k]

    flag = True
    for k in range(M):
        flag &= (tA[k] >= X)

    #print(i, tA, tans)

    if flag:
        ans = min(ans, tans)

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

Submission status: Accepted

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

CA = []
for i in range(N):
    CA.append([int(j) for j in input().split()])

min_money = 100000 ** N + 1
for i in range(2**N):
    money = 0
    result = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            money += CA[j][0]
            for n in range(1, M+1):
                result[n-1] += CA[j][n]
    if money < min_money and min(result) >= X:
        min_money = money

print(min_money if min_money != 100000 ** N + 1 else -1)

Submission status: Accepted

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

result = []
for i in range(2**n):
    num = i
    memo = [0 for _ in range(m)]
    cost = 0
    for j in range(n):
        if num%2==1:
            cost += a[j][0]
            for s in range(m):
                memo[s] += a[j][s+1]
        num >>= 1
    if all(i >= x for i in memo):
        result.append(cost)

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

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
li = []
for t in range(n):
    li.append(list(map(int, input().split())))
price_list = []
for bit in range(1, 2**n):
    index_list = []
    for i in range(n):
        if bit & 1<<i:
            index_list.append(i)

    c = 0
    for t in range(1,m+1):
        s = 0
        for i in index_list:
            s += li[i][t]
        if s >= k:
            c += 1
        else:
            break

    if c == m:
        p = 0
        for i in index_list:
            p += li[i][0]
        price_list.append(p)

if len(price_list):
    print(min(price_list))
else:
    print('-1')

Submission status: Accepted

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

C=[]
A=[[] for i in range(N)]

for i in range(N):
    temp = list(map(int,input().split()))
    C.append(temp[0])
    A[i]= temp[1:]
    
Min = 10**9

    
for i in range(1<<N):
    cost=0
    result = [0]*M
    
    for j in range(N):
        
        if(i>>j&1):
            cost+=C[j]
        else:
            continue
        for z in range(M):
            result[z] += A[j][z]
            
    flg = True
    
    for s in range(M):
        if result[s] < X:
            flg = False
    
    if flg ==True:
        Min = min(Min,cost)
        
        
if Min ==10**9:
    print(-1)
else:
    print(Min)

Submission status: Accepted

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

# 参考書の選択パターン作成
patterns=[]
for i in range(n):
    patterns.append(itertools.combinations(tmp,i+1))
# 全ての参考書を購入しても条件を満たせないときは-1
for arg in range(m):
    point=0
    for book in books:
        point+=book[arg+1]
    if point<x:
        print(-1)
        exit()

# すべての参考書のパターン
for pattern in patterns:
    # ある参考書のパターン
    for bks in pattern:
        flg=True
        # 各アルゴリズムの時の理解度合計
        for i in range(m):
            # あるアルゴリズムのときの点数とトータルコスト
            cost=0
            point=0
            for bk in bks:
                cost+=books[bk][0]
                point+=books[bk][i+1]
            if point < x:
                # あるアルゴリズムで条件を満たさない
                flg=False
        if flg==True:
            result.append(cost)
print(min(result))

Submission status: Accepted

Solution code:
def saiki(i,cost,score_list):
    if i == N:
        if min(score_list) >= X:
            ans.append(cost)
    else:
        temp = [score_list[j]+book_lists[i][j+1] for j in range(M)]
        saiki(i+1,cost,score_list)
        saiki(i+1,cost+book_lists[i][0],temp)
 
N,M,X = map(int,input().split())
book_lists = [list(map(int, input().split())) for _ in range(N)]
ans=[]
saiki(0,0,[0]*M)
print(min(ans) if len(ans)!=0 else -1)

Submission status: Accepted

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

algo = [X] * M
b = [None] * N

for i in range(N):
    c, *l = map(int, input().split())
    b[i] = (c, l)


res = float("inf")

mask = 0
while (mask < (1<<N)):
    cost = 0
    l = [0] * M

    for i in range(N):
        if (mask & (1 << i)):
            cost += b[i][0]
            l = [b[i][1][j] + l[j] for j in range(M)]

    if all(map(lambda x: x>= X, l)):
        res = min(res, cost)

    mask += 1

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

Submission status: Accepted

Solution code:
import numpy as np

nmx = input().split(' ')

n = int(nmx[0])
m = int(nmx[1])
x = int(nmx[2])

c = []
a = []

for i in range(n):
  input_tmp = input().split(' ')
  tmp_a = []
  for j in range(m+1):
    if j == 0:
      c.append(int(input_tmp[j]))
    else:
      tmp_a.append(int(input_tmp[j]))
      
  a.append(tmp_a) 

  
bits2 = []

for i in range(2**n):
  bin_ = bin(i)[2:]
  bits2.append('0'*(n-len(bin_)) + bin_)
  
bool_ = False
minimum_money = 0

for perm in bits2:
  money = 0
  
  score = [0] * m
  for i in range(n):
    if perm[i] == '1':
      money += c[i]
      
      for j in range(m):
        score[j] += a[i][j]
        
  
  score = np.array(score)
  
  if score[score < x].shape[0]:
    continue
   
  bool_ = True
  if minimum_money > money or minimum_money == 0:
  	minimum_money = money
  

if bool_:
  print(minimum_money)
else:
  print(-1)

Submission status: Accepted

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

ans = 10**9

for i in range(2**n):
    price = 0
    score = [0]*m
    for j in range(n):
        if (i>>j) & 1 == 1:
            for k in range(m):
                score[k] += a[j][k+1]
            price += a[j][0]
        if all(l >= x for l in score):
            ans = min(ans,price)
            break


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

Submission status: Accepted

Solution code:
def cos_per_find(count, cost, skills):
    if count == N:
        if min(skills) >= X:
            return cost
        else:
            return INF
    improved_skills = [a+b for a, b in zip(skills, contents[count])]
    return min(cos_per_find(count+1, cost, skills), cos_per_find(count+1, cost+price[count], improved_skills))

INF = float('inf')
N, M, X = map(int, input().split())
price = []
contents = []
for i in range(N):
    C, *A = map(int, input().split())
    price.append(C)
    contents.append(A)
if (ans := cos_per_find(0, 0, [0]*M)) == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M, X = map(int, input().split())
C = []
A = []
for _ in [0]*N:
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)

INF = 10**10
ans = INF 
for bit in range(1 << N):
    S = [0]*M
    cost = 0
    for i in range(N):
        if bit >> i & 1:
            cost += C[i]
            for j in range(M):
                S[j] += A[i][j]

    if min(S) >= X and cost < ans:
        ans = cost

print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
ca =[list(map(int,input().split())) for i in range(N)]
ans=float('inf')
for i in range(1,2**N):
    rikaido=[0]*M
    money=0
    for j in range(N):
        if i>>j&1:
            money +=ca[j][0]
            for k in range(1,M+1):
                rikaido[k-1] += ca[j][k]
        for l in range(M):
            if all(rikaido[l] >= X for l in range(M)):
                ans=min(money,ans)
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int,input().split())
price = np.array([None]*N)
skill = [None]*N
for i in range(N):
    tmp = list(map(int,input().split()))
    price[i] = tmp[0]
    skill[i] = np.array(tmp[1:])

ans = float('inf')
for pattern in range(1<<N):
    takahashi_level = np.array([0]*M)
    sum_of_price = 0
    #print(takahashi_level)
    for mask in range(N):
        if pattern&(1<<mask):
            sum_of_price += price[mask]
            takahashi_level += skill[mask]
    #print(takahashi_level[takahashi_level>=X])
    if len(takahashi_level[takahashi_level>=X]) == M:
        ans = min(sum_of_price,ans)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []
A = []
for _ in range(N):
    s = list(map(int, input().split()))
    C.append(s[0])
    A.append(s[1:])
ans = float('INF')
for i in range(0, 1 << N):
    scores = [0] * M
    count = 0
    for j in range(N):
        if (i >> j) & 1:
            for s in range(M):
                scores[s] += A[j][s]
            count += C[j]
    if min(scores) < X:
        continue
    else:
        ans = min(ans, count)
 
if ans == float("INF"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

min_fee = 1 << 64
for purchases in range(1 << n):
    total_fee = 0
    understands = [0] * m

    for i in range(n):
        if (purchases >> i) & 1:
            total_fee += refs[i][0]
            for j in range(m):
                understands[j] += refs[i][j + 1]

    if all([understand >= x for understand in understands]) and total_fee < min_fee:
        min_fee = total_fee

print(min_fee if min_fee != 1 << 64 else -1)

Submission status: Accepted

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

costlist = []
booklist = []
for i in range(0, N):
	inpt = list(map(int, input().split()))
	costlist.append(inpt[0])
	booklist.append(inpt[1:])

def bnr(n):
	lst = []
	now = n
	for i in range(0, N):
		lst.append(now%2==1)
		now = now//2
	return lst

def pow2(n):
	now = 1
	for i in range(0, n):
		now *= 2
	return now

def judge(lst):
	for i in range(0, len(lst)):
		if lst[i] < X:
			return False
	return True

mincost = 5000000000000000

for i in range(0, pow2(N)):
	cost = 0
	lst = []
	for j in range(0, M):
		lst.append(0)
	buyornot = bnr(i)
	for j in range(0, N):
		if buyornot[j]:
			cost += costlist[j]
			for k in range(0, M):
				lst[k] += booklist[j][k]
	if judge(lst) and cost<mincost:
		mincost = cost
if mincost == 5000000000000000:
	mincost = -1
print(mincost)

Submission status: Accepted

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

MinmalCost=1e30

MaxInter=2**N-1
LenOfBin=len(bin(MaxInter)[2:])
for i in range(MaxInter+1):
    binary=bin(i)[2:].rjust(LenOfBin,"0")
    Cost=0
    Learning=np.zeros(M,)
    for j,Switch in enumerate(binary):
        if Switch=="1":
            Cost+=C[j]
            Learning+=A[j]
    if np.all(Learning>=X) and Cost<MinmalCost:
        MinmalCost=Cost
if MinmalCost==1e30:
    print(-1)
else:
    print(MinmalCost)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
dictionary = list()
for i in range(N):
    dictionary.append(list(map(int,input().split())))
# print(dictionary)

n = len(dictionary)
bit_list =list()
s = 1
for i in range(2 ** n):
    bit = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bit.append(j)  # フラグが立っていたら bag に果物を詰める
    s+=1
    # print(bit)
    bit_list.append(bit)
skill = [0]*M
skill_list = list()

cost_list=list()
# print(bit_list)

for i in range(len(bit_list)):
    ran = len(bit_list[i])
    # print(ran,"range")
    skill = [0]*M
    cost=0
    for j in range(ran):
        for k in range(M):
            skill[k] += dictionary[bit_list[i][j]][k+1]
        cost+=dictionary[bit_list[i][j]][0]

    cost_list.append(cost)
    skill_list.append(skill)
# print(skill_list)

min_cost = 10000000000000
tf = 0
for i in range(len(skill_list)):
    f = 0
    for k in range(len(skill_list[i])):
        # print(skill_list[i][k],i,k)
        if(skill_list[i][k]<X):
            # print("F")
            f = 1
            break
    # print("flag",f)
    if(f == 0):
        tf = 1
        min_cost= min(min_cost,cost_list[i])
if(tf == 0):
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]
ans = 10**111
ok = False
for i in range(2**n):
    y = [0]*(m+1)
    for j in range(n):
        if i & (1 << j):
            for k in range(m+1):
                y[k] = y[k] + ca[j][k]
    if sum(z >= x for z in y[1:]) == m:
        ans = min(ans, y[0])
        ok = True
if ok:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
# ABC167C　ビット全探索
import numpy as np

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

for i in range(n):
    a = list(map(int, input().split()))
    l.append(a)
    
ans = 99999999
sum_ = [0] * (m + 1)
for i in range(2 ** n): # 2 ** 全冊数で全購入パターンのビットセット数
    bag = []             # 買い物かごの配列
    for j in range(n):
        if ((i >> j) & 1): # 購入した本の判別 全ビットパターンで1(フラグ)を最下位ビットへシフトして1と論理積
            bag.append(l[j]) # 各場合（各ビットパターン）について購入した本をbagへいれる
    
    sum_ = [0] * (m + 1)
    for book in bag:        # 各場合（各ビットパターン）について購入した本の値段と獲得スキルを足す
        for k in range(m + 1):
            sum_[k] += book[k]
    skill_sum = sum_[1:]
    cost = sum_[0]
    if all([t >= x for t in skill_sum]):
        ans = min(ans, cost)


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

Submission status: Accepted

Solution code:
import itertools
N,M,X=map(int,input().split())
A=[0]*(N);C=[0]*(N);c=0;D=[0]*(M);m=10**5;n=0;x=[];z=0;R=[0]*N;f=-1;cost=10**7;p=0
for i in range(N):
  S=list(map(int,input().split()))
  C[i]=S[0]
  A[i]=S[1:len(S)]
#print(C)
#print(A)
for i in range(len(C)):
  x.append(i)

for i, _ in enumerate(x, 1):     
    for j in itertools.combinations(x, r=i):
        f=-1
        D=[0]*(M)
        for k in j:
          for l in range(M):
            D[l]=D[l]+A[k][l]
        for v in range(M):
          if D[v]<X:
            f=1
        if f!=1:
          for y in j:
            p=p+C[y]
          if p<cost:
            cost=p
          p=0
print(cost if cost!=10000000 else -1)

Submission status: Accepted

Solution code:
N,M,X=list(map(int,input().split()))
l=[]
ans=float("INF")
for i in range(N):
   l.append(list(map(int,input().split())))
for i in range(2**N):
   counter=[0]*M
   temp=0
   for j in range(N):
      if ((i >> j) & 1):
         for k in range(1,1+M):
            counter[k-1]+=l[j][k]
         temp+=l[j][0]
   B=len([a for a in counter if a > X-1])
   if B == M:
      ans=min(ans,temp)
if ans==float("INF"):
   print(-1)
else:
   print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = map(int, input().split(' '))
a = np.zeros([n, m])
c = np.zeros(n)

for i in range(n):
  v = list(map(int, input().split(' ')))
  a[i, :] = np.array(v[1:])
  c[i] = v[0]

INF = 10000000000000000
ans = INF

for i in range(1<<n):
  skill = np.zeros(m)
  cost = 0
  for j in range(n):
    if i & (1<<j):
      cost += c[j]
      skill += a[j]
  if all(skill >= x):
    ans = min(ans, cost)

print(int(ans) if ans != INF else -1)

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    nmx = input().split()
    n = int(nmx[0])
    m = int(nmx[1])
    x = int(nmx[2])

    infos = []
    for i in range(n):
        info = input()
        infos.append(info)

    books_str = []
    values_str = []
    for i in range(len(infos)):
        book = []
        book = infos[i].split()
        values_str.append(book[0])
        books_str.append(book[1:])

    books = []
    values = []
    for i in range(n):
        values.append(int(values_str[i]))
        temp = []
        for j in range(m):
            temp.append(int(books_str[i][j]))
        books.append(temp)

    ans = 12345678
    all = 1 << n
    for i in range(all):
        level = [0]*m
        cost = 0
        for j in range(n):
            if (i>>j) & 1:
                cost += values[j]
                for k in range(m):
                    level[k] += books[j][k]
        ok = True
        for l in range(len(level)):
            if level[l] < x:
                ok = False
        if ok:
            ans = min(ans,cost)
    if ans == 12345678:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

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

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


MAX = 100000000000	

def func(cost,a,i):
	if min(a) >= X:
		return cost
	elif i == N:
		return MAX
	total_A = [x+y for (x,y) in zip(a,A[i])]
    
	return min(func(cost + C[i],total_A,i+1),func(cost,a,i+1))
	
ans = func(0,[0]*M,0)

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

Submission status: Accepted

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

Ci, Aij = [], []
for i in range(N):
    line = input().split(" ")
    line = [int(v) for v in line]

    Ci.append(line[0])
    Aij.append(line[1:])

ans = []
def dfs(candidate):
    if len(candidate) == N:
        X_ = [0 for _ in range(M)]
        cost = 0
        for i in range(N):
            if candidate[i] == 0:
                continue
            cost += Ci[i]
            for j in range(M):
                X_[j] += Aij[i][j]
        if min(X_) >= X:
            ans.append(cost)
    else:
        for bit in range(2):
            candidate.append(bit)
            dfs(candidate)
            candidate.pop()

dfs([])
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

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

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

a=np.array(a)
result=np.array([[0]*(m+1)])
for i in range(n):
    l=list()
    for j in range(len(result)):
        l.append(a[i]+result[j])
        l.append(result[j])
    result=np.array(l)

c=list()
h=[x]*m
for line in result:
    if np.all(line[1:]>=h):
        c.append(line[0])
if len(c)==0:
    print(-1)
else:
    print(min(c))

Submission status: Accepted

Solution code:
import numpy as np
import sys
from itertools import product

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

ans = 10**9

products = list(product([0,1], repeat=n))

for _ in range(n):
    c_a = list(map(int, input().split()))
    c.append(c_a[0])
    A.append(c_a[1:])

min_price = 10**9

for p in products:
    sum_alg = [0]*m
    price = 0
    for i, pp in enumerate(p):
        if pp == 1:
            for j in range(m):
                sum_alg[j] += A[i][j]
            price += c[i]

    if min(sum_alg) >= x: 
        min_price = min(price, min_price)


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

Submission status: Accepted

Solution code:
import itertools

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

ans = 10 ** 7
for combs in itertools.product([0, 1], repeat=N):
    tCA = [0] * (M + 1)
    for i, c in enumerate(combs):
        if c:
            for j in range(M + 1):
                tCA[j] += CA[i][j]
    if sum([1 for a in tCA[1:] if a >= X]) == M:
        ans = min(ans, tCA[0])
print(-1 if ans == 10 ** 7 else ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n,m,x = map(int,input().split())
BookList = [list(map(int, input().split())) for i in range(n)]
SkillList = np.zeros(m) 
mincost = 10000000
cost = 0
NumList = list(range(n))

def python_list_add(in1, in2):
    wrk = np.array(in1) + np.array(in2)
    return wrk.tolist()


for k in range(1,ｎ+1):
    for comb in itertools.combinations(NumList, k):
        #print(comb)
        for para in comb:
            SkillList = python_list_add(SkillList,BookList[para][1:])
            cost += BookList[para][0]
        #print(SkillList)

        if min(SkillList) >= x:
            if mincost > cost:
                mincost = cost
        cost = 0
        SkillList = np.zeros(m)
 #   print('mincost,k',mincost,k)

if mincost != 10000000:
    print(mincost)
else:
    print(-1)

Submission status: Accepted

Solution code:
def dfs(i, count, res):
    global ans
    if i == n:
        if min(count) < x:
            return
        ans = min(ans, res)
        return ans
    else:
        dfs(i+1, count, res)
        dfs(i+1, [count[k-1] + l[i][k] for k in range(1, m+1)], res + l[i][0])


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

ans = 10 ** 9
dfs(0, [0] * m, 0)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for i in range(n)]
mincost = 10**111

for i in range(2**n):
  li = [0]*m
  cost = 0
  count = 0
  for j in range(n):
    if (i >> j) & 1:
      cost += ca[j][0]
      for k in range(m):
        li[k] += ca[j][1+k]
  for l in range(m):
    if li[l] >= x:
      count += 1
  if count == m:
    mincost = min(cost,mincost)
    
if mincost == 10**111:
  print(-1)
else:
  print(mincost)

Submission status: Accepted

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

for i in range(N):
  A.append(input().split())

minCost = pow(10,5) * N     # 購入金額の最安値
clearFlag = 0               # 達成可否判定
bit = "0" + str(N) + "b"    # 2進数のフォーマット指定

for i in range(pow(2,N)):
  # 購入する参考書を1、購入しない参考書を0のビットで表す
  buy = format(i, bit)
  
  # 購入金額を計算
  cost = 0
  for j in range(N):
    cost += (int(A[j][0]) * int(buy[j]))
  
  # アルゴリズムの習熟度を計算
  flag = 1
  for s in range(M):
    skill = 0
    for t in range(N):
      skill += (int(A[t][s+1]) * int(buy[t]))
    # 習熟度がXを超えているか確認
    if skill < X:
      flag = 0
      break
  
  # 全てのアルゴリズムで習熟度がXを超えていて、
  # 購入金額が暫定最安値よりも安い場合
  # 暫定最安値を更新
  if (flag == 1) & (cost <= minCost):
    clearFlag = 1
    minCost = cost

# 結果出力
if clearFlag == 1:
  print(minCost)
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

lista = np.array(lista)
judge = [X]*M
cost = 120000000000
data = [a for a in range(1,N+1)] # [1,2,3,...,N]

for i in range(1,N+1):
    j = list(itertools.combinations(data, i))
    for k in j:
        result = np.array([0]*(M+1))
        for l in k:
            result = result + lista[l-1]
        if all(result[1:]>=judge):
            if result[0]<cost:
                cost = result[0]
                m = k
c = 0

try:
    for i in m:
        c +=lista[i-1][0]
    
    print(c)
except:
    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 = 1e9
for i in range(2**N):
    cnt = [0]*(M+1)
    for j in range(N):
        if i>>j & 1:
            cnt = [x+y for (x,y) in zip(cnt,CA[j])]
    if len([i for i in cnt[1:] if i>=X]) == M:
        ans = min(ans, cnt[0])
print(ans if ans<1e9 else -1)

Submission status: Accepted

Solution code:
def bit():
    n, m, x = map(int, input().split())
    books = [list(map(int, input().split())) for _ in range(n)]
    ans = 99999999999999999
    for i in range(2 ** n):
        cost = 0
        level = [0] * (m)
        for j in range(n):
            if ((i >> j) & 1):
                cost += books[j][0]
                for k in range(m):
                    level[k] += books[j][k+1]

        if level and min(level) >= x:
            ans = min(ans, cost)

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


if __name__ == "__main__":
    bit()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
from collections import Counter
ct = Counter()
Ass = []
ans = []
N, M, X = map(int, input().split())
for i in range(N):
	Ass.append(list(map(int, input().split())))

for z in range(M):	
	B = []
	for i in range(N):
		B.append(Ass[i][z])
	D = []
	for i in range(1, N+1):
		for j in combinations(Ass, i):
			flag = True
			d = [0]*(M+1)
			for k in j:  # (2, 7, 3)
				for l in range(M+1):
					d[l] += k[l]
			for x in range(1, M+1):
				if d[x] >= X:
					pass
				else:
					flag=False
					break
			if flag:
				ans.append(d[0])


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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
B = [list(map(int,input().split())) for i in range(N)]
ANS = 10**5 * 12 + 1
for i in range(1<<N):
    SCORE=[0]*M
    MONEY=0
    for j in range(N):
        if (1<<j) & i != 0:
            MONEY+=B[j][0]
            for k in range(M):
                SCORE[k]+=B[j][k+1]
    if min(SCORE)>=X:
        ANS=min(ANS,MONEY)
if ANS == 10**5 * 12 + 1:
    print(-1)
else:
    print(ANS)

Submission status: Accepted

Solution code:
import itertools

N,M,X = map(int,input().split())
c = []
d = [0]*(M+1)
e = []
for _ in range(N):
  c.append(list(map(int,input().split())))
for r in range(1,N+1):
  for x in itertools.combinations(c,r):
    for y in range(len(x)):
      for z in range(M+1):
        d[z] += x[y][z]
    for z in range(1,M+1):
      if d[z]<X:
        d = [0]*(M+1)
        break
      elif z == M:
        e.append(d[0])
        d = [0]*(M+1)
if len(e)>0:
  print(min(e))
else:
  print(-1)